# Efficient Ciphertext-Policy Attribute-Based Online/Offline Encryption with User Revocation

Authors: Haiying Ma; Zhanjun Wang; Zhijin Guan
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Attribute-Based Encryption (ABE) must provide an efficient revocation mechanism since a user’s private key can be compromised or expired over time. The existing revocable ABE schemes have the drawbacks of heavy computational costs on key updates and encryption operations, which make the entities for performing these operations a possible bottleneck in practice applications. In this paper, we propose an efficient Ciphertext-Policy Attribute-Based Online/Offline Encryption with user Revocation (R-CP-ABOOE). We integrate the subset difference method with ciphertext-policy ABE to significantly improve key-update efficiency on the side of the trusted party fromO(rlog⁡(N/r)) to O(r), where N is the number of users and r is the number of revoked users. To reduce the encryption burden for mobile devices, we use the online/offline technology to shift the majority of encryption work to the offline phase, and then mobile devices only need to execute a few simple computations to create a ciphertext. In addition, we exploit a novel trick to prove its selective security under the q-type assumption. Performance analysis shows that our scheme greatly improves the key-update efficiency for the trusted party and the encryption efficiency for mobile devices.


---

## Body

## 1. Introduction

Attribute-based encryption (ABE) is a promising alternative of encryption for achieving fine-grained access control of encrypted data. The notion of ABE is first proposed by Sahai and Waters [1], and then Goyal et al. [2] formalize two supplementary forms of ABE: ciphertext-policy ABE (CP-ABE) and key-policy ABE (KP-ABE). In CP-ABE [3, 4], each user possesses a private key that corresponds to his attribute set. A ciphertext is embedded into an access policy over the possible attributes. The ciphertext can be successfully decrypted by the users whose attributes satisfy the policy. Alternatively, in KP-ABE the roles are swapped: a ciphertext is associated with an access policy and the private key is related to a set of attributes.Any ABE system must provide an efficient method to revoke users since a user’s private key can be compromised or expired over time. As a practical solution to the problem for ABE, Boldyreva et al. [5] used the complete subtree method [6] to revoke users. In their scheme, a user can encrypt with the set of attributes and the current time attribute, e.g., “TIME: 2018. WEEK 16,” and the key generation center (KGC), who owns the latest revocation list, periodically broadcasts the key update component at each time slot such that all nonrevoked users can reconstruct their decryption key and utilize it decrypt ciphertexts. Subsequently, Attrapadung and Imai [7] proposed a revocable KP-ABE by using a similar method. However, the key-update work can be a system bottleneck since KGC requires broadcasting key-update component to all nonrevoked users at all time slots. Although their solutions [6, 7] reduce this work from O(N) to O(rlog⁡(N/r)), where N is the number of users and r is the number of revoked users and the key-update work still is a bottleneck. Lee et al. [8] proposed an efficiently revocable identity-based encryption using subset difference methods, which has O(r) number of group elements in an update key. We note that their idea cannot be directly used to construct revocable ABE, because a user’s identity is not related to decryption in ABE systems.At the same time, in all revocable ABE schemes, the encryption process must perform a lot of exponentiations, and the encryption cost grows with the complexity of access policy or number of attributes. If a mobile device performs the encryption task, battery power and encryption time will be a large problem. To significantly reduce the encryption cost for mobile device, a few online/offline ABE schemes [9–12] are proposed, and move the majority of encryption computations into an offline phase. Mobile device only needs to execute a few simple calculations to create a ciphertext. However, the existing online/offline ABE schemes cannot revoke users. Therefore, our goal is to integrate the subset difference method [6, 8] with ABE to significantly decrease the key update work, and use the online/offline technique to greatly improve the encryption efficiency for mobile devices.In this work, we propose an efficient ciphertext-policy attribute-based online/offline encryption with user revocation. In particular, our contributions have three aspects as follows:( 1 ) We present a novel technique that may integrate CP-ABE with the Subset Difference (SD) methodology to significantly improve the key-update efficiency for KGC. In SD scheme, an assigned key for each subset is dependent on other keys, so we may categorize all subsets into different groups. For each group GT in SD, we assign a random polynomial fGT(x)=aGTx+α to it, where aGT is a random value that is uniquely assigned to the group GT and α is the master secret key. Using this linear polynomial, we split the master secret key α into two shares fGT1 and fGTT, where T is an update time and is a greater than 1 positive integer. The share fGT1 is used to build a private key which is related to user’s attribute set in CP-ABE as usual, and the other share fGTT is used to build an update key which is related to the update time T. Then KGC periodically broadcasts the update keys, and any nonrevoked user can reconstruct his decryption key. Since all revoked users possess the same share fGT1, they cannot collude to reconstruct a decryption key. Therefore, our scheme may provide the security against collusion attacks.( 2 ) To greatly reduce the encryption cost for mobile devices, we employ the online/offline technique of [8] to split encryption process into the offline phase and the online phase. The offline encryption first performs a majority of encryption task before the plaintext and its access policy are known. Once the specifications are given, the online encryption only executes a few simple calculations to produce a ciphertext by using the offline-ciphertexts pool that is similar to the reference [8]. Especially, the offline work can be executed by a high-performance computer, and then lightweight devices can quickly run the online encryption on the move without greatly draining the battery.( 3 ) We present a new method to prove the security of our scheme. Based on the CP-ABE’s access policy A∗ and a challenge update time T∗, we construct a new challenge access policy A∗∗=A∗∧T∗,i. e., we may obtain A∗∗ by appending a well-designed vector to A∗. Next, we can create the public parameters needed in the proof. Moreover, unlike the complete subtree method, the intersection of the covering collection of nonrevoked users and the private key of the revoked users is not empty. It leads to impossibility to construct the update key on the time T∗. We solve this problem by reasonably assigning the users’ location in the binary tree. Our scheme is proved to be selectively secure under theq-type assumption. The above method may be of independent interest in the security proof of the revocable CP-ABE scheme. Compared with the related works, our scheme can significantly improve the key-update efficiency for the trusted party from O(rlog⁡(N/r)) to O(r) and the encryption efficiency for mobile devices, where N is the number of users and r is the number of revoked users, and greatly decrease the number of group elements in the update key.ABE is a useful cryptographic technology to protect private data and achieve fine-grained access control simultaneously [12, 13], many variants of ABE were proposed to realize promising properties,e.g., efficient large universe ABE [4], ABE with verifiable outsourced decryption [14–16], traceable-then-revocable ABE [17, 18], CP-ABE against key-delegation abuse [19], the fully-secure ABE [11], ABE resilience against continuous auxiliary-inputs leakage [20, 21].To reduce the encryption cost of ABE, a few works [9–12] presented the online/offline ABE by the online/offline cryptography [22–25], but their schemes cannot revoke users. To satisfy the practical requirement that users’ access rights can be revoked dynamically, many revocable ABE schemes have been proposed [10–20]. The core idea of the works [5, 7, 26–31] utilizes the complete subtree scheme of NNL [8] to revoke user’s private key. Lee et al. [8] proposed a revocable identity-based encryption to reduce the size of the update key. Sahai et al. [29] constructed a few ABE schemes of revocable storage by providing a ciphertext delegation means without any interaction with data owners. Datta et al. [32] uses the subset difference to directly revoke users in KP-ABE systems. Nevertheless, all the existing revocable ABE schemes have the drawbacks of heavy computational costs on key updates and encryption operations.Therefore, it will be indispensable to reduce the heavy computational overhead on the key update work and the encryption task. Different from prior works, we integrate the SD method with the online/offline technique in the CP-ABE system, which not only may efficiently revoke users, but also can significantly improve the key-update efficiency and encryption efficiency.We review some preliminaries in Section2. The definition and security model of our scheme is defined in Section 3. We propose an efficient ciphertext-policy attribute-based online/offline encryption with user revocation and prove its selective security in Section 4. Performance analysis is given in Section 5. Finally, we conclude this work in Section 6.


## 2. Preliminaries

In this section, we first elaborate the definitions of bilinear group and the complexity assumption for our R-CP-ABOOE scheme. Then we state a brief review of access structures and linear secret-sharing schemes (LSSS). Finally, we introduce the notions of full binary tree and the subset difference method.


### 2.1. Bilinear Group and the Complexity Assumptions

We give some notations. Forn∈N, we define [n]=1,2,…,n, and for n1,n2,…,nk∈N, n1,n2,…,nk=n1×n2×⋯×[nk]. For l,n∈N, by Zpl×n we denote a set of matrices of size l×n with elements in Zp. A row vector is denoted as y1,y2,…,yn, while a column vector is denoted as y1,y2,…,ynT, where T denotes the transpose of the vector.Definition 1 (bilinear group).
LetG, GT be multiplicative cyclic groups of prime order p, and we define a symmetric bilinear map e: G×G→GT with the following properties: (1) bilinearity: for all g1,g2∈G, and c,d∈Zp, we have e(g1c,g2d)=e(g1,g2)cd; (2) nondegeneracy: ∃u∈G, e(u,u)≠1; (3) computability: the bilinear map e and the group operations in G and GT are efficiently computable. Then the tuple (p,G,GT,e) is called a bilinear group.Definition 2 (q-type assumption [4]).
Given a security parameterκ∈N, an integer q, a group generator G(κ) that outputs the bilinear group description (p,G,GT,e), chooses a random element g∈G and q+2 random values a,s,b1,b2,…,bq∈Zp and computes the following terms E:(1)g,gs;gai,gbj,gsbj,gaibj,gai/bj2∀i,j∈q,q;gai/bj∀i,j∈2q,qandi≠q+1;gaibj/bj′2∀i,j′,j∈2q,q,qandj≠j′;gsaibj/bj′,gsaibj/bj′2∀i,j′,j∈q,q,qandj≠j′.If any probabilistic polynomial-time (PPT) adversary obtains the bilinear group description (p,G,GT,e) and the above terms E, it cannot distinguish the element F=eg,gsaq+1∈GT from a random element R∈GT with a nonnegligible advantage. We say that theq-typeassumption holds in the bilinear group (p,G,GT,e).


### 2.2. Access Structures and Linear Secret Sharing Scheme (LSSS)

Definition 3 (access structures [4]).
LetI=I1,I2,…,Ik be a set of attributes. A collection A⊆2I is monotone if ∀C,D and C∈A, C⊆D then D∈A. An access structure is a collection A of nonempty subsets of I,i.e., A⊆2I∖⌀. The authorized sets are defined as the sets in A, and the unauthorized sets are the sets not in A.Definition 4 (LSSS [4]).
LetI=I1,I2,…,Ik, a function ρ: {1,2,…,l}→I. A secret-sharing scheme Π over a set of attributes I is called linear over Zp if (1) the shares for each attribute form a vector over Zp; (2) there is a matrix A called the share-generation matrix for Π. The matrix A has l rows and n columns. For each row i=1,2,…,l, the ith row of A is labeled by an attribute ρ(i). Let the column vector v=s,r2,…,rnT, where s∈Zp is the shared secret and r2,…,rn∈Zp are randomly picked, then A∙v is the vector of l shares of the secret s according to Π. The share Avi belongs to the attribute ρ(i). Reconstruction property. Suppose the scheme Π is an LSSS for the access structure A. Let ω∈A be any authorized set, and I⊆{1,2,…,l} is defined as I={i:ρ(i)∈ω}. If si are valid shares of any secret s, there are constants ci∈Zpi∈I that satisfy ∑i∈Icisi=s.


### 2.3. Full Binary Tree

We follow the terminologies on the full binary tree in [8]. Let T be a full binary tree with N leaves. Each user ID is assigned to a unique leaf node id. In the tree, it has 2N-1 nodes, for η=1 to 2N-1, let vη denote a node, and each edge is labelled as a bit 1 or 0, at the right branch corresponds to bit 1 and the left branch corresponds to bit 0. The identifier Lη of a node vη is defined as the unique bitstring which is the bitstring of all edges in the path from the root to the node vη. For each node vη, its depth dη is the size of the path from the root to vη.LetSη denote the set of leaves in the subtree that is rooted at the node vη. For any two nodes vη, vθ so that vη is an ancestor node of vθ, Sη,θ is defined as the set of all leaves that are descendants of vη but not vθ,i.e., Sη,θ=Sη–Sθ.LetGT identify a group, and a group’s tagGT is described as the collection of subset Sη,θ such that vη is the same node and other different nodes vθ have the same depth, and let GT=Lη∥dθ. In our scheme, we randomly choose aGT∈Zp and specify a polynomial fGT(x)=aGTx+α once for one groupGT to revoke users.LetR be the list of all revoked users, ST(R) be the Steiner Tree induced by the root node and the set R, that is, the minimal subtree of the tree T connects the root node and all the leaves in R.


### 2.4. Subset Difference Method

As a general revocation methodology, Subset-Cover framework [6] includes both the complete subtree method and the subset difference (SD) method, and SD was presented as an improvement on the complete subtree scheme. The definition of SD is given as follows.Definition 5 (subset difference).
The SD scheme for the setN=1,2,…,N of all users consists of four algorithms: Setup, Assign, Cover, Match, which are described as following:
SD.Setup ( N ) → ( T , S ): The setup algorithm inputs all users N and sets a full binary tree T with at least N leaves, where N is the total number of users. It assigns a unique leaf of T once to a user. For any two nodes vη,vθ∈T such that vη is an ancestor node of vθ and it gets the collection S of subset {Sη,θ}. It outputs the tree T and the collection S.
SD.Assign ( T , I D ) → P V I D: Given the full binary tree T and a user ID∈N, the assignment algorithm assigns a leaf id of T to the user ID. Let (v0,vk1,…,vkn=id) denote the path from the root v0 to the leafid and a private set PVID be an empty one. For all vη,vθ∈{v0,vk1,…,vkn} such that vη is an ancestor of vθ and it adds all subset Sη,θ to PVID. Then it outputs the user’s private collection PVID=Sη,θ.
SD.Cover ( T , R ) → C V R: Given the full binary tree T and the set R of revoked users, the covering algorithm gets the Steiner Tree ST(R) and sets a subtree TR=ST(R) and then constructs a covering collection CVR by iteratively removing nodes from the treeTR untilTR is made up of only a single node as follows:
( 1 ) It derives two leaves vi and vj from the tree TR and then finds their least-common ancestor v which does not contain any other leaf in this tree TR. Let vl and vk be two child of v where vl is a father node of vi and vk is a father node of vj. If TR has only one leaf, it sets vi=vj to be a leaf node and sets v=vl=vk to be the root of v.
( 2 ) If vk≠vj, it adds the subset Sk,j to CVR; similarly, if vl≠vi, it adds the subset Sl,i to CVR.
( 3 ) It deletes all descendants of v fromTRand lets v be a leaf.
It outputs the covering collectionCVR=Si,j.
SD.Match ( P V I D , C V R ) → ( S η , θ , S i , j )/⊥: Given a private collection PVID=Sη,θ and a covering collection CVR=Si,j, this matching algorithm searches two subsets Sη,θ∈PVID and Si,j∈CVR so that η=i, θ≠j, and the nodes vθ and vj have the same depth, i.e., dθ=dj. If it finds two subsets, then it outputs (Sη,θ,Si,j). Otherwise, it fails.
Remark. In the SD scheme, the revocation list R cannot be empty. Let r be the size of R,i.e., r≥1. To address the case r=0, we may add a dummy user that is revoked so that R′=r′=r+1.


## 2.1. Bilinear Group and the Complexity Assumptions

We give some notations. Forn∈N, we define [n]=1,2,…,n, and for n1,n2,…,nk∈N, n1,n2,…,nk=n1×n2×⋯×[nk]. For l,n∈N, by Zpl×n we denote a set of matrices of size l×n with elements in Zp. A row vector is denoted as y1,y2,…,yn, while a column vector is denoted as y1,y2,…,ynT, where T denotes the transpose of the vector.Definition 1 (bilinear group).
LetG, GT be multiplicative cyclic groups of prime order p, and we define a symmetric bilinear map e: G×G→GT with the following properties: (1) bilinearity: for all g1,g2∈G, and c,d∈Zp, we have e(g1c,g2d)=e(g1,g2)cd; (2) nondegeneracy: ∃u∈G, e(u,u)≠1; (3) computability: the bilinear map e and the group operations in G and GT are efficiently computable. Then the tuple (p,G,GT,e) is called a bilinear group.Definition 2 (q-type assumption [4]).
Given a security parameterκ∈N, an integer q, a group generator G(κ) that outputs the bilinear group description (p,G,GT,e), chooses a random element g∈G and q+2 random values a,s,b1,b2,…,bq∈Zp and computes the following terms E:(1)g,gs;gai,gbj,gsbj,gaibj,gai/bj2∀i,j∈q,q;gai/bj∀i,j∈2q,qandi≠q+1;gaibj/bj′2∀i,j′,j∈2q,q,qandj≠j′;gsaibj/bj′,gsaibj/bj′2∀i,j′,j∈q,q,qandj≠j′.If any probabilistic polynomial-time (PPT) adversary obtains the bilinear group description (p,G,GT,e) and the above terms E, it cannot distinguish the element F=eg,gsaq+1∈GT from a random element R∈GT with a nonnegligible advantage. We say that theq-typeassumption holds in the bilinear group (p,G,GT,e).


## 2.2. Access Structures and Linear Secret Sharing Scheme (LSSS)

Definition 3 (access structures [4]).
LetI=I1,I2,…,Ik be a set of attributes. A collection A⊆2I is monotone if ∀C,D and C∈A, C⊆D then D∈A. An access structure is a collection A of nonempty subsets of I,i.e., A⊆2I∖⌀. The authorized sets are defined as the sets in A, and the unauthorized sets are the sets not in A.Definition 4 (LSSS [4]).
LetI=I1,I2,…,Ik, a function ρ: {1,2,…,l}→I. A secret-sharing scheme Π over a set of attributes I is called linear over Zp if (1) the shares for each attribute form a vector over Zp; (2) there is a matrix A called the share-generation matrix for Π. The matrix A has l rows and n columns. For each row i=1,2,…,l, the ith row of A is labeled by an attribute ρ(i). Let the column vector v=s,r2,…,rnT, where s∈Zp is the shared secret and r2,…,rn∈Zp are randomly picked, then A∙v is the vector of l shares of the secret s according to Π. The share Avi belongs to the attribute ρ(i). Reconstruction property. Suppose the scheme Π is an LSSS for the access structure A. Let ω∈A be any authorized set, and I⊆{1,2,…,l} is defined as I={i:ρ(i)∈ω}. If si are valid shares of any secret s, there are constants ci∈Zpi∈I that satisfy ∑i∈Icisi=s.


## 2.3. Full Binary Tree

We follow the terminologies on the full binary tree in [8]. Let T be a full binary tree with N leaves. Each user ID is assigned to a unique leaf node id. In the tree, it has 2N-1 nodes, for η=1 to 2N-1, let vη denote a node, and each edge is labelled as a bit 1 or 0, at the right branch corresponds to bit 1 and the left branch corresponds to bit 0. The identifier Lη of a node vη is defined as the unique bitstring which is the bitstring of all edges in the path from the root to the node vη. For each node vη, its depth dη is the size of the path from the root to vη.LetSη denote the set of leaves in the subtree that is rooted at the node vη. For any two nodes vη, vθ so that vη is an ancestor node of vθ, Sη,θ is defined as the set of all leaves that are descendants of vη but not vθ,i.e., Sη,θ=Sη–Sθ.LetGT identify a group, and a group’s tagGT is described as the collection of subset Sη,θ such that vη is the same node and other different nodes vθ have the same depth, and let GT=Lη∥dθ. In our scheme, we randomly choose aGT∈Zp and specify a polynomial fGT(x)=aGTx+α once for one groupGT to revoke users.LetR be the list of all revoked users, ST(R) be the Steiner Tree induced by the root node and the set R, that is, the minimal subtree of the tree T connects the root node and all the leaves in R.


## 2.4. Subset Difference Method

As a general revocation methodology, Subset-Cover framework [6] includes both the complete subtree method and the subset difference (SD) method, and SD was presented as an improvement on the complete subtree scheme. The definition of SD is given as follows.Definition 5 (subset difference).
The SD scheme for the setN=1,2,…,N of all users consists of four algorithms: Setup, Assign, Cover, Match, which are described as following:
SD.Setup ( N ) → ( T , S ): The setup algorithm inputs all users N and sets a full binary tree T with at least N leaves, where N is the total number of users. It assigns a unique leaf of T once to a user. For any two nodes vη,vθ∈T such that vη is an ancestor node of vθ and it gets the collection S of subset {Sη,θ}. It outputs the tree T and the collection S.
SD.Assign ( T , I D ) → P V I D: Given the full binary tree T and a user ID∈N, the assignment algorithm assigns a leaf id of T to the user ID. Let (v0,vk1,…,vkn=id) denote the path from the root v0 to the leafid and a private set PVID be an empty one. For all vη,vθ∈{v0,vk1,…,vkn} such that vη is an ancestor of vθ and it adds all subset Sη,θ to PVID. Then it outputs the user’s private collection PVID=Sη,θ.
SD.Cover ( T , R ) → C V R: Given the full binary tree T and the set R of revoked users, the covering algorithm gets the Steiner Tree ST(R) and sets a subtree TR=ST(R) and then constructs a covering collection CVR by iteratively removing nodes from the treeTR untilTR is made up of only a single node as follows:
( 1 ) It derives two leaves vi and vj from the tree TR and then finds their least-common ancestor v which does not contain any other leaf in this tree TR. Let vl and vk be two child of v where vl is a father node of vi and vk is a father node of vj. If TR has only one leaf, it sets vi=vj to be a leaf node and sets v=vl=vk to be the root of v.
( 2 ) If vk≠vj, it adds the subset Sk,j to CVR; similarly, if vl≠vi, it adds the subset Sl,i to CVR.
( 3 ) It deletes all descendants of v fromTRand lets v be a leaf.
It outputs the covering collectionCVR=Si,j.
SD.Match ( P V I D , C V R ) → ( S η , θ , S i , j )/⊥: Given a private collection PVID=Sη,θ and a covering collection CVR=Si,j, this matching algorithm searches two subsets Sη,θ∈PVID and Si,j∈CVR so that η=i, θ≠j, and the nodes vθ and vj have the same depth, i.e., dθ=dj. If it finds two subsets, then it outputs (Sη,θ,Si,j). Otherwise, it fails.
Remark. In the SD scheme, the revocation list R cannot be empty. Let r be the size of R,i.e., r≥1. To address the case r=0, we may add a dummy user that is revoked so that R′=r′=r+1.


## 3. Definition and Security Model of R-CP-ABOOE

The R-CP-ABOOE scheme consists of eight algorithms: Setup, KeyGen, KeyUpdate, DecKey,Encoff, Encon, Dec, and Rev, which are defined as follows:Setup ( κ , U , N ) → ( p k , m s k , Λ , R ): This setup algorithm inputs a security parameter κ, the universe of attributes U, and all users N and outputs the system public key pk, the master secret keymsk, the state Λ and the revocation list R.KeyGen ( m s k , ( I D , ω ) , Λ , p k ) → s k ( I D , ω ): This key-generation algorithm inputs the master secret keymsk, a user identity-attribute pair (ID,ω), the state Λ, and public keypk and outputs the user’s private key sk(ID,ω).KeyUpdate ( T , R , m s k , Λ , p k ) → ( Λ , u k T , R ): This key-update algorithm inputs a time T, the revocation list R, the master secret key msk, the current state Λ, and the public key pk and outputs the updated state Λ and an update key ukT,R.DecKey ( s k I D , ω , u k T , R , p k ) → d k ( I D , ω ) , T     ∖⊥: This decryption-key algorithm inputs a user’s private key sk(ID,ω), an update key ukT,R, and the public keypk and outputs a decryption key dk(ID,ω),T or a failure ⊥.Enc off ( p k ) → ( O C m a i n , O C a t t ): This offline-encryption algorithm can independently create an arbitrary number of main OCmain and many attribute modules OCatt by using the public keypk and then stores them in a pool of offline-ciphertexts. This algorithm can be performed by high-performance computer.Enc on ( ( O C m a i n , O C a t t ) , m , A , T ) → C T A , T: This online-encryption algorithm first picks one main module OCmain and some attribute modules OCatt,τ from the pool of offline-ciphertexts. Then it inputs a message m, an access policy A, and a time T and outputs a ciphertext CTA,T. This algorithm is a true encryption process and is performed by the constrained-computation devices.Dec ( C T A , T , d k ( I D , ω ) , T , p k ) → m    ∖⊥: This decryption algorithm inputs a ciphertext CTA,T, a decryption key dk(ID,ω),T, and the public keypk and outputs a messagem or a failure notation ⊥.Rev ( I D , T , R , Λ ) → R ′: This revocation algorithm inputs an identity ID, a revocation time T, the current revocation list R, and the state Λ and outputs the updated revocation list R′.The correctness of R-CP-ABOOE: ForSetup(κ,U,N)→(pk,msk,Λ,R),KeyGen(msk,(ID,ω),Λ,pk)→sk(ID,ω),KeyUpdate(T,R,msk,Λ,pk)→(ukT,R,Λ), Encon(Encoff(pk),m,A,T)→CTA,T, it is satisfied by the two cases:( 1 ) If (ID∉R), thenDecKey(sk(ID,ω),ukT,R,pk)→dk(ID,ω),T. OtherwiseDecKey(sk(ID,ω),ukT,R,pk)→⊥.( 2 ) If (ω∈A)∧T=T′, thenDec(CTA,T′,dk(ID,ω),T,pk)→m. OtherwiseDec(CTA,T′,dk(ID,ω),T,pk)→⊥.The selective security of R-CP-ABOOE is formally described as the following game between a challengerS and an adversary A:Init: The adversary A submits the challenge policy A∗, the challenge time T∗, the revocation list R∗ on the challenge time T∗ to the challenger S.Setup: S runsSetup(κ,U,N)→(pk,msk,Λ,R) and sendspk to A.Phase 1: A adaptively requests a polynomial number of the following oracles simulated by S:( 1 ) The private Key Generation oracle KG·. A submits an identity-attribute pair (ID,ω) to S, then S runsKeyGen(msk,(ID,ω),Λ,pk)→sk(ID,ω) and sends sk(ID,ω) to A.( 2 ) The Key Update oracle KU(·). A submits a timeT to S, then S runsKeyUpdate(T,R,msk,Λ,pk)→(ukT,R,Λ) and sends ukT,R to A.( 3 ) The Revocation oracle R·. A submits an identity-time pair (ID,T) to S, then S runsRev(ID,T,R,Λ)→R′ and sends R′ to A.This phase must be satisfied by the restricted condition as follows:(1) for each query (ID,ω), whereω satisfies the challenge policy A∗ and R· must be queried on (ID,T) for any T≤T∗. (2)KU(·) and R· are queried on the time which cannot be less than the time of all previous queries.Challenge: A submits two messages m0 and m1 with equal length to S. S picks a random bit c∈0,1 and runs Encon(Encoff(pk),T,A∗,mc)→CT∗ and sends CT∗ to A.Phase 2: The same as Phase 1.Guess: A outputs a guess bit c′.Only ifc′=c, does A win this game. Therefore, we define the advantage of A as AdvA=Prc′=c-1/2 in the above game.Definition 6.
Our scheme is selectively secure if any PPT adversary can break the above game with negligible advantage.


## 4. Our Scheme and Security Proof

### 4.1. Our Intuition

At a high level we explain how to construct our scheme. We uses the full binary tree withN leaves as in the subset difference (SD) method [8]. Each user ID can be assigned to a leaf nodeid which is not appointed yet. In SD, all the subsets can be categorized into different groups, and each group GT is assigned a random secret one-degree polynomial fGT(x) such that fGT(0)=α, where α is the master secret key. Let X=e(g,g)s. Our scheme uses Xα=e(g,g)αs∈GT to encrypt a message, where s is a random number.Given the revoked users’ setR on the time T, the KGC utilizes the master secret key to build an update key corresponding to each subset in Cover(R). Only the nonrevoked userID can retrieve a subset Sη,θ ∈ Cover(R) such that ID∈Sη,θ, and the userID can compute XfGT(T). Simultaneously, only the userID whose attribute setωsatisfies the access policy associated with ciphertext can compute XfGT(1). Because the function fGT(x) is a first-order polynomial, using these two elements, we can obtain XfGT(0) by interpolation in the exponent. Obviously, the revoked users only can obtain the same element XfGT(1), and then they cannot get two different elements of the one-degree polynomial fGT(x). Therefore, our scheme provides security against collusion attacks.


### 4.2. Our Construction

Forx,i∈Zp and a set of indexes I⊆Zp, a Lagrange coefficient Δi,I(x) may be defined as (2)Δi,Ix=∏j∈I,j≠ix-ji-j.Our R-CP-ABOOE scheme is described as follows:Setup ( κ , U , N ) → ( p k , m s k , Λ , R ): This setup algorithm first runs the group generator G(κ) to get bilinear groupsG, GT of prime orderp, U=Zp, and randomly picks g,h,u,v,w∈G, and α∈Zp. Let a user list LID contain a tuple (ID,id) as an empty one, and let a function list Lf contain a tuple (GT,fGT(x)) for a group’s tagGT as an empty one. Let M be the message space and the size of a message M=2nM. Let a hash function H: 0,1∗→0,1nM. It runs SD.Setup(N) to get the full binary tree T. Let C denote the collection of all sets Sη,θ of T. For each Sη,θ∈C, it makes GT=Lη∥dθ and runs the following: if (GT,∗)∉Lf, then it chooses randomly aGT∈Zp and specifies a polynomial fGT(x)=aGTx+α once for one group GT and saves (GT,fGT(x)) into Lf. Finally, it sets an empty revocation list R, a state Λ=(T,LID), and outputs a master secret key msk=(Lf,α) and system public key pk=(p,g,h,u,v,w,Φ=eg,gα,H(·)).KeyGen ( m s k , ( I D , ω ) , Λ , p k ) ⟶ ( s k ( I D , ω ) , Λ ): This key-generation algorithm inputs the master secret keymsk, a user identity-attribute pair (ID,ω) where the set ω=(A1,A2,…,Aω), the state Λ=(T,LID) and public key pk. For the user ID, it chooses an unassigned leaf node id from Λ and stores the tuple (ID,id) into LID, and runs SD. Assign(T,ID) to obtain PVID=Sη,θ. Next, for each Sη,θ∈PVID, it sets the group GT=Lη∥dθ and retrieves (GT,fGT(x)) from Lf. Second, it chooses random values r,r1,r2,…,rω∈Zp and computes K0=gfGT1wr, K1=gr. For τ=1 to ω, it computes K2,τ=grτ, K3,τ=uAτhrτv-r and outputs(3)pskID,ω,Sη,θ=K0,K1,K2,τ,K3,ττ∈ω.Finally, it outputs the updated state Λ and a private key (4)skID,ω=ID,ω,PVID,pskID,τ,Sη,θSη,θ∈PVID.KeyUpdate ( T , R , m s k , Λ , p k ) → ( Λ , u k T , R ): This algorithm inputs an update time T, the revocation list R, the master secret key msk, the state Λ=(T,LID), and the public key pk. First it defines the identities of revoked users on the timeT according to R, and uses LID to define the revoked index set RI. It runs SD.Cover(T,R) to obtain CVRI=Sη,θ. Second, for each Sη,θ∈CVRI, it sets GT=Lη∥dθ and retrieves (GT,fGT(x)) from Lf. Then it chooses random values t,t1∈Zp and computes a time-constrained update key (5)tukT,Sη,θ=U0=gfGTTwt,U1=gt,U2=gt1,U3=uTht1v-t.Finally, it outputs the updated state Λ and an update key (6)ukT,R=CVRI,tukT,Sη,θSη,θ∈CVRI.DecKey ( s k I D , ω , u k T , R , p k ) → d k ( I D , ω ) , T    ∖⊥: This decryption-key generation algorithm inputs a user private key sk(ID,ω), an update key ukT,R andpk. First, if ID∉R, then it callsSD.Match(CVRI,PVID) to get (Sη,θ,Sη′,θ′) such that Sη,θ∈CVRI, Sη′,θ′∈PVID, η=η′∧dθ=dθ′∧θ≠θ′. Otherwise, it exports ⊥.Second, it retrievestukT,Sη,θ from ukT,R and pskID,ω,Sη′,θ′ from sk(ID,ω). Since η=η′∧dθ=dθ′, tukT,Sη,θ, and pskID,ω,Sη′,θ′ share the same fGT(x) for GT=Lη∥dθ. It sets I=1,T and computes two Lagrange coefficients Δ1,I(0) and ΔT,I(0). It chooses random values t′,t1′,r′,r1′,r2′,…,rω′∈Zp and computes a decryption key as (7)E0=U0ΔT,I0wt′,E1=U1ΔT,I0gt′,E2=U2ΔT,I0gt1′,E3=U3ΔT,I0uTht1′v-t′,D0=K0∆1,I0wr′,D1=K1Δ1,I0gr′.For τ=1 to ω, it computes (8)D2,τ=K2,τΔ1,I0grτ′,D3,τ=K3,τΔ1,I0uAτhrτ′v-r′.Finally, it outputs a decryption-keydk(ID,ω),T=((ID,ω),D0,D1,D2,τ,D3,ττ∈ω,E0,E1,E2,E3).E n c o f f ( p k ) → ( O C m a i n , O C a t t ): This offline-encryption algorithm can construct an arbitrary number of main modules OCmain and attribute modules OCatt by using pk. It first choose randomly s∈Zp and computes key=eg,gαs and C0=gs. It sets the main module OCmain=(s,key,C0). Then it picks randomly x1,x2,x3∈Zp and computes C1=wx1vx3, C2=ux2h-x3, and C3=gx3 to obtain an attribute module OCatt=(x1,x2,x3,C1,C2,C3). Using the above process, it can obtain a lot of main modules OCmain and attribute modules OCatt.E n c o n ( O C m a i n , O C a t t , τ τ ∈ [ l + 1 ] , m , A ( A , ρ ) , T ) → C T A , T: Suppose that A is an l×n access matrix, this online-encryption algorithm first picks one main module OCmain=(s,key,C0) and l+1 attribute modules OCatt=(x1,x2,x3,C1,C2,C3) available from the pool. For τ=1,2,…,l+1, it sets the attribute module OCatt,τ=(x1,τ,x2,τ,x3,τ,C1,τ,C2,τ,C3,τ). It randomly chooses y2,…,yn∈Zp and sets the vector s=s,y2,…,ynT, where T denotes the transpose of the vector. It computes a vector λ1,λ2,…,λlT=As. Finally, for τ=1 to l, it calculates C4,τ=λτ-x1,τ, C5,τ=-x3,τ(ρ(τ)-x2,τ). It computes K′=H(key,C3,1,C3,2,…,C3,l+1), C4,l+1=s-x1,l+1, and C5,l+1=-x3,l+1(T–x2,l+1). It outputs a ciphertext CTA,T=(A(A,ρ),T,m⊕K′,C0,{C1,τ,C2,τ,C3,τ,C4,τ,C5,τ}τ∈[l+1]).Dec ( C T A , T , d k ( I D , ω ) , T , p k ) → m      ∖⊥: This algorithm takes in a ciphertext CTA,T=(A(A,ρ),T,m⊕K′,C0,{C1,τ,C2,τ,C3,τ,C4,τ,C5,τ}τ∈[l+1]), a decryption key dk(ID,ω),T=((ID,ω),D0,D1,D2,τ,D3,ττ∈ω,E0,E1,E2,E3) and the public key pk. If ω satisfies the policy A(A,ρ), then it sets Γ={τ∣ρ(τ)∈ω} and computes constants wτ∈Zp such that ∑τ∈ΓwτAτ=1,0,…,0 where Aτ is the τ-th row of matrix A, and it denotes ρ(τ)=Ai, where i is the index of attribute ρ(τ) in ω. It recovers eg,gαs by computing(9)eC0,D0ew∑τ∈ΓC4,τwτ,D1∏τ∈ΓeC1,τ,D1eC2,τuC5,τ,D2,ieC3,τ,D3,iwτ=eg,gfGT1Δ1,I0s,(10)eC0,E0eC1,l+1wC4,l+1,E1eC2,l+1uC5,l+1,E2eC3,l+1,E3=eg,gfGTTΔT,I0s,(11)eg,gfGT1Δ1,I0seg,gfGTTΔT,I0s=eg,gαs=key,(12)K′=Hkey,C3,1,C3,2,…,C3,l+1,m⊕K′⊕K′=m.Rev ( I D , T , R , Λ ) → R ′: This revocation algorithm takes as inputs an identity ID, a revocation time T, the revocation list R, and the state Λ=(T,LID). If (ID,∗)∉Lu, then it outputs ⊥ if the private key of the pair (ID,ω) was not generated. Otherwise, it adds (ID,T) to R. It outputs the updated revocation list R′.


### 4.3. Security Proof

Theorem 7.
Our scheme is selectively secure under chosen plaintext attacks if theq-type assumption holds. That is, all PPT adversaries have at most a negligible advantage in breaking the R-CP-ABOOE scheme.Proof.
Suppose there exists a PPT adversaryA that breaks the R-CP-ABOOE scheme with a nonnegligible advantage, and then a simulator S can solve theq-type assumption with a nonnegligible advantage by using the given terms of theq-type assumption.
Init: S receives the given terms from theq-type assumption, a challenge policy (A∗,ρ∗), a challenge time T∗ and the revocation list R∗ on the time T∗ from A. The challenge matrix A∗ is an l×n matrix and satisfies the restriction l+1, n≤q, and the map ρ∗: [l]→Zp. Let M be the message space and the size of a message M=2nM. Let a hash function H: 0,1∗⟶0,1nM. It sets an n-dimensional vector v=1,0,…,0 that is related to the challenge time T∗. S builds a new policy (A∗∗,ρ∗∗), where ρ∗∗: [l+1]→U∪T∗,(13)A∗∗=A∗v,ρ∗∗i=ρ∗ii∈lT∗i=l+1.Since U∩T∗=⌀, we know that, for any attribute set ω⊂U, ω satisfies A∗∗ if and only if ω satisfies A∗, and for time T that satisfies A∗∗ if and only if T=T∗.
Setup: S implicitly sets α=aq+1+α1 where a,q are assigned in the assumption and a random exponent α1∈Zp is known only to S. Especially, this way α is well distributed and a is hidden to A from information theory. Then S proceeds as follows:
( 1 ) It calls SD.Setup(N) to get the full binary tree T with 2N leaves and sets C to be the collection of all sets Sη,θ of T. Let LID and Lf be an empty set respectively. For each user ID∈R∗, it allocates ID∈N to an unsigned leaf id that belongs to the left subtree of T and stores (ID,id) in LID. According to R∗⊆N, it uses LID to define the revoked index set RI∗. For each ID∉R∗, it allocates ID∈N to an unsigned leaf id that belongs to the right subtree of T and stores (ID,id) in LID.
( 2 ) It callsSD.Assign(T,RI∗) to obtain ⋃id∈RI∗(PVID). Then it sets Fixedsubset(R∗)=⋃id∈RI∗(PVID). It sets function list Lf as follows: if Sη,θ ∈ Fixedsubset(R∗), it chooses a random value y∈Zp and stores (GT=Lη∥dθ,(x=1,y)) in LID. Otherwise, for each Sη,θ∈C∖Fixedsubset(R∗), it picks random value y∈Zp and stores GT=Lη∥dθ,T∗,y in Lf such that GT=Lη∥dθ,∗∉Lf. Note that it employs the Lagrange interpolation method to implicitly define fGT(x) by two points (0,α) and (x,y). Next, it sets an empty revocation list LR and sets Λ=(T,LID). It selects random values v1,u1,h1∈Zp and gives to A the following public parameters:(14)g=g,w=ga,v=gv1·ga/bl+1·∏j,k∈l,ngak/bjAj,k∗,u=gu1·ga/bl+12·∏j,k∈l,ngak/bj2Aj,k∗,h=gh1∏j,k∈l,ngak/bj2-ρ∗jAj,k∗·g-aT∗/bl+12,eg,gα=ega,gaqeg,gα1.
Finally, it publishes public keyspk=(g,w,v,u,h,eg,gα,H(·)).
Phases 1: A inquiries adaptively a polynomial number of private key generation, update key and user revocation oracles. If this is a private key query for (ID,ω), where the attribute set ω=(A1,A2,…,Aω), then S proceeds as follows.
Ifωdoes not satisfy (A∗,ρ∗) from the pair (ID,ω), denote ω⊭(A∗,ρ∗), then ω⊭(A∗∗,ρ∗∗). It executes the following steps:
( 1 ) It first constructs temporal private key components for the point (0,α) as follows. Since ω⊭(A∗∗,ρ∗∗), there exists a vector w=w1,w2,…,wn∈Zpn such that w1 = -1 and Ai∗∗·w=0 for all i∈I={i∣i∈l+1∧ρ∗∗(i)∈ω}, and then it picks r′∈Zp and implicitly sets r=r′+w1aq+w2aq-1+⋯+wnaq-n+1=r′+∑i∈[n]wiaq+1-i and computes(15)P0=gαwr=gα1gar′∏i=2ngaq+2-iwi,P1=gr=gr′∏i∈ngaq+1-iwi.In addition, for each attribute Aτ∈ω, it randomly selects rτ′∈Zp and implicitly sets(16)rτ=rτ′+r′∑i′∈l+1,ρ∗∗i′∉ωbi′Aτ-ρ∗∗i′+∑i,i′∈n,l+1,ρ∗∗i′∉ωwibi′aq+1-iAτ-ρ∗∗i′.Then it may compute the terms (17)P2,τ=grτ=grτ′·∏i′∈l+1,ρ∗∗i′∉ωgbi′r′/Aτ-ρ∗∗i′·∏i,i′∈n,l+1,ρ∗∗i′∉ωgbi′aq+1-i′wi/Aτ-ρ∗∗i′,(18)P3,τ=uAτhrτv-r=uAτhrτ′P2,τg-rτ′u1Aτ+h1·∏i′,j.k∈l+1,l+1,n,ρ∗∗i′∉ωgbi′akbj-2r′Aj,k∗∗Aτ-ρ∗∗j/Aτ-ρ∗∗i′·∏i,i′,j.k∈n,l+1,l+1,n,ρ∗∗i′∉ω,j≠i′∨i≠kgbi′aq+1+k-ibj-2Aτ-ρ∗∗jwiAj,k∗∗Aτ-ρ∗∗i′-1·v-r′∏i∈ngaq+1-i-v1wi·∏i,j.k∈n,l+1,n,i≠kgaq+1+k-ibj-1-wiAj,k∗∗.
( 2 ) If (ID,∗)∈LID, then it loads (ID,id) from LID. Otherwise it allocates ID∈N to a unique indexid that is not assigned previously and stores (ID,id) in LID. Then it callsSD.Assign(T,ID) to obtain PVid={Sη,θ}.
( 3 ) For each Sη,θ∈PVid, it retrieves (GT=Lη∥dθ,(x,y)) from Lf. If Sη,θ ∈ Fixedsubset(R∗), it must have x=1 from Lf. It chooses random value r,r1,r2,…,rω∈Zp and computes a private key by implicitly setting fGT(1)=y as K0=gywr and K1=gr, and for τ=1 to ω, it computes K2,τ=grτ, K3,τ=(uAτh)rτv-r. Then, it outputs the updated state Λ and a private key (19)skID,ω=ID,ω,K0,K1,K2,τ,K3,ττ∈ωSη,θ∈PVID∧FixedsubsetR∗.Otherwise, for each Sη,θ∉FixedsubsetR∗, since x is a random value, then it has x≠T∗. Let I={0,T∗}, it computes two Lagrange coefficients Δ0,I(1) and ∆T∗,I(1). Then it chooses random exponents r′′,r1′′,r2′′,···,rk′′∈Zp and computes a private key as K0=P0Δ0,I1gy∆T∗,I(1)wr′′ and K1=P1Δ0,I1gr′′, and for τ=1 to ω, it computes K2,τ=P2,τΔ0,I1grτ′′, and K3,τ=P3,τΔ0,I1v-r′′uAτhrτ′′. Then, it outputs the updated state Λ and a private key (20)skID,ω=ID,ω,K0,K1,K2,τ,K3,ττ∈ωSη,θ∈PVID∧Sη,θ∉FixedsubsetR∗).
Ifω satisfies (A∗,ρ∗), it must set ID∈R∗ and executes the following steps:
( 1 ) It loads (ID,id) from LID. Then it callsSD.Assign(BT,ID) to obtain PVID=Sη,θ.
( 2 ) For each Sη,θ∈PVID, it retrieves (GT=Lη∥dθ,(1,y)) from Lf. Since Sη,θ ∈ Fixedsubset(R∗), it must have x=1 from Lf.. It chooses random value r,r1,r2,…,rk∈Zp and computes a private key by implicitly setting fGT(1)=y as K0=gywr, K1=gr, and for τ=1 to ω, K2,τ=grτ, and K3,τ=uAτhrτv-r. Then, it outputs the updated state Λ and a private key (21)skID,ω=ID,ω,K0,K1,K2,τ,K3,ττ∈ωSη,θ∈PVid.
IfA requests the update key query for time T and T≠T∗, then T⊭A∗∗,ρ∗∗. S performs the four steps:
( 1 ) Since T⊭A∗∗,ρ∗∗, there exists a vector w=-1,0,…,0T∈Zpn, for all i∈I={i∣i∈l+1∧ρ∗∗(i)=T}=⌀, and then it picks t′∈Zp and implicitly sets t=t′-aq and computes(22)B0=gαwt=gα1gat′,B1=gt=gt′g-aq.In addition, it randomly selects t1′∈Zp and implicitly sets(23)t1=t1′+t′∑i′∈l+1bi′T-ρ∗∗i′-∑i′∈l+1bi′aqT-ρ∗∗i′.Then it may compute the terms (24)B2=gt1=gt1′·∏i′∈l+1gbi′t′/T-ρ∗∗i′·∏i′∈l+1gbi′aq-1/T-ρ∗∗i′,(25)B3=uTht1v-t=uTht1′B2g-t1′u1T+h1·∏i′,j,k∈l+1,l+1,ngbi′akbj-2t′Aj,k∗∗T-ρ∗∗j/T-ρ∗∗i′·∏i′,j,k∈l+1,l+1,n,j≠i′∨k≠1gbi′aq+kbj-2-T-ρ∗∗jAj,k∗∗T-ρ∗∗i′-1·v-t′gaqv1·∏j,k∈l+1,n,k≠1gaq+kbj-1Aj,k∗∗.
( 2 ) It defines the revocation set on the time T from R, and uses LID to define the revoked index set RI. It runs SD.Cover(T,R) to obtain CVRI=Sη,θ.
( 3 ) For each Sη,θ∈CVRI, it retrieves (GT=Lη∥dθ,(x,y)) from Lf and sets I=0,1. For each Sη,θ ∈ Fixedsubset(R∗), it chooses random values t,t1∈Zp and computes a time-constrained update key by implicitly setting fGT1=y as (26)tukT,Sη,θ=U0=B0Δ0,ITgyΔ1,ITwt,U1=B1Δ0,ITgt,U2=B2Δ0,ITgt1,U3=B3Δ0,ITv-tuTht1.For each Sη,θ ∉ FixedsubsetR∗, it sets I=0,T∗ and computes two Lagrange coefficients Δ0,I(T) and ΔT∗,I(T). It chooses random values t′′,t1′′∈Zp and computes a time-constrained update key as (27)tukT,Sη,θ=U0=B0Δ0,ITgyΔT∗,ITwt′′,U1=B1Δ0,ITgt′′,U2=B2Δ0,ITgt1′′,U3=B3Δ0,ITv-t′′uTht1′′.
( 4 ) Finally, it outputs the updated state Λ and an update key (28)ukT,R=CVRI,tukT,Sη,θSη,θ∈CVRI.
IfT=T∗, it executes the following three steps:
( 1 ) It sets R=R∗ and obtains the revoked index set RI∗ of the revocation list R∗ by LID. It does not run SD.Cover(T,R∗) to obtain CVRI∗ but assigns all the nonrevoked users to the right subtree of T;i.e., CVRI∗ can be described as the set {Sη,θ∣η is the root node of the right subtree of T, θ is the descendant node of η}. Thus, CVRI∗∩ Fixedsubset(R∗)=⌀.
( 2 ) For each Sη,θ∈CVRI∗, it sets GT=Lη∥dθ and retrieves (GT,(T∗,y)) from Lf. Then it chooses random values t,t1∈Zp and computes a time-constrained update key by implicitly setting fGTT∗=y as (29)tukT,Sη,θ=U0=gywt,U1=gt,U2=gt1,U3=uT∗ht1v-t.
( 3 ) Finally, it outputs the updated state Λ and an update key (30)ukT,R=CVRI,tukT,Sη,θSη,θ∈CVRI.
Challenge: The adversary A submits a pair of messages (m0,m1) with the same length to the simulator S. Then S flips a random bit c∈0,1 and constructs: key=F·eg,gsα1, C0=gs, where F is the challenge term and gs is the appropriate term of the assumption.
S implicitly sets a vector y=(s,sa+y2,…,saq+1yn), where y2,…,yn are chosen uniformly at random from Zp. Therefore, the secret s and the vector y are uniformly distributed. Especially s is hidden for A from information theory. Let λ=A∗yT. For each row τ∈l, it implicitly sets(31)λτ=∑i∈nAτ,i∗sai-1+∑i∈nAτ,i∗yi=∑i∈nAτ,i∗sai-1+λτ′.Let the terms λτ′ be known to S. For each row of Aτ∗, S implicitly sets tτ=-sbτ. Since bτ’s are hidden for A from information theory, the terms tτ are uniformly distributed as well. S also picks random values x1,τ′,x2,τ′,x3,τ′∈Zp and implicitly sets x1,τ=λτ-x1,τ′, x2,τ=ρ(τ)∗-x2,τ′·bτ-1, and x3,τ=-sbτ. As a result, A computes(32)C1,τ=wx1,τvx3,τ=wλτgsbτ-v1w-x1,τ′∏j,k∈l+1,n∧j≠τgsakbτbj-1-Aj,k∗∗,(33)C2,τ=ux2,τh-x3,τ=u-x2,τ′gsbτ-u1ρ∗∗τ+h1∏j,k∈l,n∧j≠τgsakbτbj-2-Aj,k∗∗ρ∗∗τ-ρ∗∗j,(34)C3,τ=gx3,τ=g-sbτ,C4,τ=λτ-x1,τ=x1,τ′,C5,τ=-x3,τρ∗∗τ-x2,τ=x2,τ′,For τ=l+1, S implicitly sets tl+1=-sbl+1 and also picks random values x1,l+1′,x2,l+1′∈Zp and implicitly sets x1,l+1=s-x1,l+1′, x2,l+1=T∗-x2,l+1′, and x3,l+1=-sbl+1. As a result, A computes(35)C1,l+1=wx1,l+1vx3,l+1=gsbl+1-v1∏j,k∈l+1,n∧j≠τgsakbl+1bj-1-Aj,k∗∗,(36)C2,l+1=ux2,l+1h-x3,l+1=gsbl+1-u1T∗+h1∏j,k∈l+1,ngsakbl+1bj-2-Aj,k∗∗T∗-ρ∗∗j,(37)C3,l+1=gx3,l+1=g-sbl+1,C4,l+1=s-x1,l+1=x1,l+1′,(38)C5,l+1=-x3,l+1T∗-x2,l+1=x2,l+1′,K′=Hkey,C3,1,C3,2,…,C3,l+1.Finally, S submits the ciphertext CT∗={A∗,ρ∗,T∗,C0=mc⊕K′, C1,τ,C2,τ,C3,τ,C4,τ,C5,ττ∈[l+1]} to A.
Phase 2: it is the same as Phase 1.
Guess: A outputs a guess c′ for the challenge ciphertext CT∗. If c′=c, S outputs 0, it means that the challenge term is F=eg,g-saq+1. Otherwise, it outputs 1.
IfF=eg,g-saq+1, A played the real security game, since key=F·eg,gαs, K′=H(key,C3,1,C3,2,…,C3,l+1), and C0=mc⊕K′. Otherwise, if F is a random value of GT, then the advantage of A is 0. Therefore, if A wins the above security game with a nonnegligible advantage, then S can solve theq-type assumption with a nonnegligible advantage by using the given terms of theq- type assumption.


## 4.1. Our Intuition

At a high level we explain how to construct our scheme. We uses the full binary tree withN leaves as in the subset difference (SD) method [8]. Each user ID can be assigned to a leaf nodeid which is not appointed yet. In SD, all the subsets can be categorized into different groups, and each group GT is assigned a random secret one-degree polynomial fGT(x) such that fGT(0)=α, where α is the master secret key. Let X=e(g,g)s. Our scheme uses Xα=e(g,g)αs∈GT to encrypt a message, where s is a random number.Given the revoked users’ setR on the time T, the KGC utilizes the master secret key to build an update key corresponding to each subset in Cover(R). Only the nonrevoked userID can retrieve a subset Sη,θ ∈ Cover(R) such that ID∈Sη,θ, and the userID can compute XfGT(T). Simultaneously, only the userID whose attribute setωsatisfies the access policy associated with ciphertext can compute XfGT(1). Because the function fGT(x) is a first-order polynomial, using these two elements, we can obtain XfGT(0) by interpolation in the exponent. Obviously, the revoked users only can obtain the same element XfGT(1), and then they cannot get two different elements of the one-degree polynomial fGT(x). Therefore, our scheme provides security against collusion attacks.


## 4.2. Our Construction

Forx,i∈Zp and a set of indexes I⊆Zp, a Lagrange coefficient Δi,I(x) may be defined as (2)Δi,Ix=∏j∈I,j≠ix-ji-j.Our R-CP-ABOOE scheme is described as follows:Setup ( κ , U , N ) → ( p k , m s k , Λ , R ): This setup algorithm first runs the group generator G(κ) to get bilinear groupsG, GT of prime orderp, U=Zp, and randomly picks g,h,u,v,w∈G, and α∈Zp. Let a user list LID contain a tuple (ID,id) as an empty one, and let a function list Lf contain a tuple (GT,fGT(x)) for a group’s tagGT as an empty one. Let M be the message space and the size of a message M=2nM. Let a hash function H: 0,1∗→0,1nM. It runs SD.Setup(N) to get the full binary tree T. Let C denote the collection of all sets Sη,θ of T. For each Sη,θ∈C, it makes GT=Lη∥dθ and runs the following: if (GT,∗)∉Lf, then it chooses randomly aGT∈Zp and specifies a polynomial fGT(x)=aGTx+α once for one group GT and saves (GT,fGT(x)) into Lf. Finally, it sets an empty revocation list R, a state Λ=(T,LID), and outputs a master secret key msk=(Lf,α) and system public key pk=(p,g,h,u,v,w,Φ=eg,gα,H(·)).KeyGen ( m s k , ( I D , ω ) , Λ , p k ) ⟶ ( s k ( I D , ω ) , Λ ): This key-generation algorithm inputs the master secret keymsk, a user identity-attribute pair (ID,ω) where the set ω=(A1,A2,…,Aω), the state Λ=(T,LID) and public key pk. For the user ID, it chooses an unassigned leaf node id from Λ and stores the tuple (ID,id) into LID, and runs SD. Assign(T,ID) to obtain PVID=Sη,θ. Next, for each Sη,θ∈PVID, it sets the group GT=Lη∥dθ and retrieves (GT,fGT(x)) from Lf. Second, it chooses random values r,r1,r2,…,rω∈Zp and computes K0=gfGT1wr, K1=gr. For τ=1 to ω, it computes K2,τ=grτ, K3,τ=uAτhrτv-r and outputs(3)pskID,ω,Sη,θ=K0,K1,K2,τ,K3,ττ∈ω.Finally, it outputs the updated state Λ and a private key (4)skID,ω=ID,ω,PVID,pskID,τ,Sη,θSη,θ∈PVID.KeyUpdate ( T , R , m s k , Λ , p k ) → ( Λ , u k T , R ): This algorithm inputs an update time T, the revocation list R, the master secret key msk, the state Λ=(T,LID), and the public key pk. First it defines the identities of revoked users on the timeT according to R, and uses LID to define the revoked index set RI. It runs SD.Cover(T,R) to obtain CVRI=Sη,θ. Second, for each Sη,θ∈CVRI, it sets GT=Lη∥dθ and retrieves (GT,fGT(x)) from Lf. Then it chooses random values t,t1∈Zp and computes a time-constrained update key (5)tukT,Sη,θ=U0=gfGTTwt,U1=gt,U2=gt1,U3=uTht1v-t.Finally, it outputs the updated state Λ and an update key (6)ukT,R=CVRI,tukT,Sη,θSη,θ∈CVRI.DecKey ( s k I D , ω , u k T , R , p k ) → d k ( I D , ω ) , T    ∖⊥: This decryption-key generation algorithm inputs a user private key sk(ID,ω), an update key ukT,R andpk. First, if ID∉R, then it callsSD.Match(CVRI,PVID) to get (Sη,θ,Sη′,θ′) such that Sη,θ∈CVRI, Sη′,θ′∈PVID, η=η′∧dθ=dθ′∧θ≠θ′. Otherwise, it exports ⊥.Second, it retrievestukT,Sη,θ from ukT,R and pskID,ω,Sη′,θ′ from sk(ID,ω). Since η=η′∧dθ=dθ′, tukT,Sη,θ, and pskID,ω,Sη′,θ′ share the same fGT(x) for GT=Lη∥dθ. It sets I=1,T and computes two Lagrange coefficients Δ1,I(0) and ΔT,I(0). It chooses random values t′,t1′,r′,r1′,r2′,…,rω′∈Zp and computes a decryption key as (7)E0=U0ΔT,I0wt′,E1=U1ΔT,I0gt′,E2=U2ΔT,I0gt1′,E3=U3ΔT,I0uTht1′v-t′,D0=K0∆1,I0wr′,D1=K1Δ1,I0gr′.For τ=1 to ω, it computes (8)D2,τ=K2,τΔ1,I0grτ′,D3,τ=K3,τΔ1,I0uAτhrτ′v-r′.Finally, it outputs a decryption-keydk(ID,ω),T=((ID,ω),D0,D1,D2,τ,D3,ττ∈ω,E0,E1,E2,E3).E n c o f f ( p k ) → ( O C m a i n , O C a t t ): This offline-encryption algorithm can construct an arbitrary number of main modules OCmain and attribute modules OCatt by using pk. It first choose randomly s∈Zp and computes key=eg,gαs and C0=gs. It sets the main module OCmain=(s,key,C0). Then it picks randomly x1,x2,x3∈Zp and computes C1=wx1vx3, C2=ux2h-x3, and C3=gx3 to obtain an attribute module OCatt=(x1,x2,x3,C1,C2,C3). Using the above process, it can obtain a lot of main modules OCmain and attribute modules OCatt.E n c o n ( O C m a i n , O C a t t , τ τ ∈ [ l + 1 ] , m , A ( A , ρ ) , T ) → C T A , T: Suppose that A is an l×n access matrix, this online-encryption algorithm first picks one main module OCmain=(s,key,C0) and l+1 attribute modules OCatt=(x1,x2,x3,C1,C2,C3) available from the pool. For τ=1,2,…,l+1, it sets the attribute module OCatt,τ=(x1,τ,x2,τ,x3,τ,C1,τ,C2,τ,C3,τ). It randomly chooses y2,…,yn∈Zp and sets the vector s=s,y2,…,ynT, where T denotes the transpose of the vector. It computes a vector λ1,λ2,…,λlT=As. Finally, for τ=1 to l, it calculates C4,τ=λτ-x1,τ, C5,τ=-x3,τ(ρ(τ)-x2,τ). It computes K′=H(key,C3,1,C3,2,…,C3,l+1), C4,l+1=s-x1,l+1, and C5,l+1=-x3,l+1(T–x2,l+1). It outputs a ciphertext CTA,T=(A(A,ρ),T,m⊕K′,C0,{C1,τ,C2,τ,C3,τ,C4,τ,C5,τ}τ∈[l+1]).Dec ( C T A , T , d k ( I D , ω ) , T , p k ) → m      ∖⊥: This algorithm takes in a ciphertext CTA,T=(A(A,ρ),T,m⊕K′,C0,{C1,τ,C2,τ,C3,τ,C4,τ,C5,τ}τ∈[l+1]), a decryption key dk(ID,ω),T=((ID,ω),D0,D1,D2,τ,D3,ττ∈ω,E0,E1,E2,E3) and the public key pk. If ω satisfies the policy A(A,ρ), then it sets Γ={τ∣ρ(τ)∈ω} and computes constants wτ∈Zp such that ∑τ∈ΓwτAτ=1,0,…,0 where Aτ is the τ-th row of matrix A, and it denotes ρ(τ)=Ai, where i is the index of attribute ρ(τ) in ω. It recovers eg,gαs by computing(9)eC0,D0ew∑τ∈ΓC4,τwτ,D1∏τ∈ΓeC1,τ,D1eC2,τuC5,τ,D2,ieC3,τ,D3,iwτ=eg,gfGT1Δ1,I0s,(10)eC0,E0eC1,l+1wC4,l+1,E1eC2,l+1uC5,l+1,E2eC3,l+1,E3=eg,gfGTTΔT,I0s,(11)eg,gfGT1Δ1,I0seg,gfGTTΔT,I0s=eg,gαs=key,(12)K′=Hkey,C3,1,C3,2,…,C3,l+1,m⊕K′⊕K′=m.Rev ( I D , T , R , Λ ) → R ′: This revocation algorithm takes as inputs an identity ID, a revocation time T, the revocation list R, and the state Λ=(T,LID). If (ID,∗)∉Lu, then it outputs ⊥ if the private key of the pair (ID,ω) was not generated. Otherwise, it adds (ID,T) to R. It outputs the updated revocation list R′.


## 4.3. Security Proof

Theorem 7.
Our scheme is selectively secure under chosen plaintext attacks if theq-type assumption holds. That is, all PPT adversaries have at most a negligible advantage in breaking the R-CP-ABOOE scheme.Proof.
Suppose there exists a PPT adversaryA that breaks the R-CP-ABOOE scheme with a nonnegligible advantage, and then a simulator S can solve theq-type assumption with a nonnegligible advantage by using the given terms of theq-type assumption.
Init: S receives the given terms from theq-type assumption, a challenge policy (A∗,ρ∗), a challenge time T∗ and the revocation list R∗ on the time T∗ from A. The challenge matrix A∗ is an l×n matrix and satisfies the restriction l+1, n≤q, and the map ρ∗: [l]→Zp. Let M be the message space and the size of a message M=2nM. Let a hash function H: 0,1∗⟶0,1nM. It sets an n-dimensional vector v=1,0,…,0 that is related to the challenge time T∗. S builds a new policy (A∗∗,ρ∗∗), where ρ∗∗: [l+1]→U∪T∗,(13)A∗∗=A∗v,ρ∗∗i=ρ∗ii∈lT∗i=l+1.Since U∩T∗=⌀, we know that, for any attribute set ω⊂U, ω satisfies A∗∗ if and only if ω satisfies A∗, and for time T that satisfies A∗∗ if and only if T=T∗.
Setup: S implicitly sets α=aq+1+α1 where a,q are assigned in the assumption and a random exponent α1∈Zp is known only to S. Especially, this way α is well distributed and a is hidden to A from information theory. Then S proceeds as follows:
( 1 ) It calls SD.Setup(N) to get the full binary tree T with 2N leaves and sets C to be the collection of all sets Sη,θ of T. Let LID and Lf be an empty set respectively. For each user ID∈R∗, it allocates ID∈N to an unsigned leaf id that belongs to the left subtree of T and stores (ID,id) in LID. According to R∗⊆N, it uses LID to define the revoked index set RI∗. For each ID∉R∗, it allocates ID∈N to an unsigned leaf id that belongs to the right subtree of T and stores (ID,id) in LID.
( 2 ) It callsSD.Assign(T,RI∗) to obtain ⋃id∈RI∗(PVID). Then it sets Fixedsubset(R∗)=⋃id∈RI∗(PVID). It sets function list Lf as follows: if Sη,θ ∈ Fixedsubset(R∗), it chooses a random value y∈Zp and stores (GT=Lη∥dθ,(x=1,y)) in LID. Otherwise, for each Sη,θ∈C∖Fixedsubset(R∗), it picks random value y∈Zp and stores GT=Lη∥dθ,T∗,y in Lf such that GT=Lη∥dθ,∗∉Lf. Note that it employs the Lagrange interpolation method to implicitly define fGT(x) by two points (0,α) and (x,y). Next, it sets an empty revocation list LR and sets Λ=(T,LID). It selects random values v1,u1,h1∈Zp and gives to A the following public parameters:(14)g=g,w=ga,v=gv1·ga/bl+1·∏j,k∈l,ngak/bjAj,k∗,u=gu1·ga/bl+12·∏j,k∈l,ngak/bj2Aj,k∗,h=gh1∏j,k∈l,ngak/bj2-ρ∗jAj,k∗·g-aT∗/bl+12,eg,gα=ega,gaqeg,gα1.
Finally, it publishes public keyspk=(g,w,v,u,h,eg,gα,H(·)).
Phases 1: A inquiries adaptively a polynomial number of private key generation, update key and user revocation oracles. If this is a private key query for (ID,ω), where the attribute set ω=(A1,A2,…,Aω), then S proceeds as follows.
Ifωdoes not satisfy (A∗,ρ∗) from the pair (ID,ω), denote ω⊭(A∗,ρ∗), then ω⊭(A∗∗,ρ∗∗). It executes the following steps:
( 1 ) It first constructs temporal private key components for the point (0,α) as follows. Since ω⊭(A∗∗,ρ∗∗), there exists a vector w=w1,w2,…,wn∈Zpn such that w1 = -1 and Ai∗∗·w=0 for all i∈I={i∣i∈l+1∧ρ∗∗(i)∈ω}, and then it picks r′∈Zp and implicitly sets r=r′+w1aq+w2aq-1+⋯+wnaq-n+1=r′+∑i∈[n]wiaq+1-i and computes(15)P0=gαwr=gα1gar′∏i=2ngaq+2-iwi,P1=gr=gr′∏i∈ngaq+1-iwi.In addition, for each attribute Aτ∈ω, it randomly selects rτ′∈Zp and implicitly sets(16)rτ=rτ′+r′∑i′∈l+1,ρ∗∗i′∉ωbi′Aτ-ρ∗∗i′+∑i,i′∈n,l+1,ρ∗∗i′∉ωwibi′aq+1-iAτ-ρ∗∗i′.Then it may compute the terms (17)P2,τ=grτ=grτ′·∏i′∈l+1,ρ∗∗i′∉ωgbi′r′/Aτ-ρ∗∗i′·∏i,i′∈n,l+1,ρ∗∗i′∉ωgbi′aq+1-i′wi/Aτ-ρ∗∗i′,(18)P3,τ=uAτhrτv-r=uAτhrτ′P2,τg-rτ′u1Aτ+h1·∏i′,j.k∈l+1,l+1,n,ρ∗∗i′∉ωgbi′akbj-2r′Aj,k∗∗Aτ-ρ∗∗j/Aτ-ρ∗∗i′·∏i,i′,j.k∈n,l+1,l+1,n,ρ∗∗i′∉ω,j≠i′∨i≠kgbi′aq+1+k-ibj-2Aτ-ρ∗∗jwiAj,k∗∗Aτ-ρ∗∗i′-1·v-r′∏i∈ngaq+1-i-v1wi·∏i,j.k∈n,l+1,n,i≠kgaq+1+k-ibj-1-wiAj,k∗∗.
( 2 ) If (ID,∗)∈LID, then it loads (ID,id) from LID. Otherwise it allocates ID∈N to a unique indexid that is not assigned previously and stores (ID,id) in LID. Then it callsSD.Assign(T,ID) to obtain PVid={Sη,θ}.
( 3 ) For each Sη,θ∈PVid, it retrieves (GT=Lη∥dθ,(x,y)) from Lf. If Sη,θ ∈ Fixedsubset(R∗), it must have x=1 from Lf. It chooses random value r,r1,r2,…,rω∈Zp and computes a private key by implicitly setting fGT(1)=y as K0=gywr and K1=gr, and for τ=1 to ω, it computes K2,τ=grτ, K3,τ=(uAτh)rτv-r. Then, it outputs the updated state Λ and a private key (19)skID,ω=ID,ω,K0,K1,K2,τ,K3,ττ∈ωSη,θ∈PVID∧FixedsubsetR∗.Otherwise, for each Sη,θ∉FixedsubsetR∗, since x is a random value, then it has x≠T∗. Let I={0,T∗}, it computes two Lagrange coefficients Δ0,I(1) and ∆T∗,I(1). Then it chooses random exponents r′′,r1′′,r2′′,···,rk′′∈Zp and computes a private key as K0=P0Δ0,I1gy∆T∗,I(1)wr′′ and K1=P1Δ0,I1gr′′, and for τ=1 to ω, it computes K2,τ=P2,τΔ0,I1grτ′′, and K3,τ=P3,τΔ0,I1v-r′′uAτhrτ′′. Then, it outputs the updated state Λ and a private key (20)skID,ω=ID,ω,K0,K1,K2,τ,K3,ττ∈ωSη,θ∈PVID∧Sη,θ∉FixedsubsetR∗).
Ifω satisfies (A∗,ρ∗), it must set ID∈R∗ and executes the following steps:
( 1 ) It loads (ID,id) from LID. Then it callsSD.Assign(BT,ID) to obtain PVID=Sη,θ.
( 2 ) For each Sη,θ∈PVID, it retrieves (GT=Lη∥dθ,(1,y)) from Lf. Since Sη,θ ∈ Fixedsubset(R∗), it must have x=1 from Lf.. It chooses random value r,r1,r2,…,rk∈Zp and computes a private key by implicitly setting fGT(1)=y as K0=gywr, K1=gr, and for τ=1 to ω, K2,τ=grτ, and K3,τ=uAτhrτv-r. Then, it outputs the updated state Λ and a private key (21)skID,ω=ID,ω,K0,K1,K2,τ,K3,ττ∈ωSη,θ∈PVid.
IfA requests the update key query for time T and T≠T∗, then T⊭A∗∗,ρ∗∗. S performs the four steps:
( 1 ) Since T⊭A∗∗,ρ∗∗, there exists a vector w=-1,0,…,0T∈Zpn, for all i∈I={i∣i∈l+1∧ρ∗∗(i)=T}=⌀, and then it picks t′∈Zp and implicitly sets t=t′-aq and computes(22)B0=gαwt=gα1gat′,B1=gt=gt′g-aq.In addition, it randomly selects t1′∈Zp and implicitly sets(23)t1=t1′+t′∑i′∈l+1bi′T-ρ∗∗i′-∑i′∈l+1bi′aqT-ρ∗∗i′.Then it may compute the terms (24)B2=gt1=gt1′·∏i′∈l+1gbi′t′/T-ρ∗∗i′·∏i′∈l+1gbi′aq-1/T-ρ∗∗i′,(25)B3=uTht1v-t=uTht1′B2g-t1′u1T+h1·∏i′,j,k∈l+1,l+1,ngbi′akbj-2t′Aj,k∗∗T-ρ∗∗j/T-ρ∗∗i′·∏i′,j,k∈l+1,l+1,n,j≠i′∨k≠1gbi′aq+kbj-2-T-ρ∗∗jAj,k∗∗T-ρ∗∗i′-1·v-t′gaqv1·∏j,k∈l+1,n,k≠1gaq+kbj-1Aj,k∗∗.
( 2 ) It defines the revocation set on the time T from R, and uses LID to define the revoked index set RI. It runs SD.Cover(T,R) to obtain CVRI=Sη,θ.
( 3 ) For each Sη,θ∈CVRI, it retrieves (GT=Lη∥dθ,(x,y)) from Lf and sets I=0,1. For each Sη,θ ∈ Fixedsubset(R∗), it chooses random values t,t1∈Zp and computes a time-constrained update key by implicitly setting fGT1=y as (26)tukT,Sη,θ=U0=B0Δ0,ITgyΔ1,ITwt,U1=B1Δ0,ITgt,U2=B2Δ0,ITgt1,U3=B3Δ0,ITv-tuTht1.For each Sη,θ ∉ FixedsubsetR∗, it sets I=0,T∗ and computes two Lagrange coefficients Δ0,I(T) and ΔT∗,I(T). It chooses random values t′′,t1′′∈Zp and computes a time-constrained update key as (27)tukT,Sη,θ=U0=B0Δ0,ITgyΔT∗,ITwt′′,U1=B1Δ0,ITgt′′,U2=B2Δ0,ITgt1′′,U3=B3Δ0,ITv-t′′uTht1′′.
( 4 ) Finally, it outputs the updated state Λ and an update key (28)ukT,R=CVRI,tukT,Sη,θSη,θ∈CVRI.
IfT=T∗, it executes the following three steps:
( 1 ) It sets R=R∗ and obtains the revoked index set RI∗ of the revocation list R∗ by LID. It does not run SD.Cover(T,R∗) to obtain CVRI∗ but assigns all the nonrevoked users to the right subtree of T;i.e., CVRI∗ can be described as the set {Sη,θ∣η is the root node of the right subtree of T, θ is the descendant node of η}. Thus, CVRI∗∩ Fixedsubset(R∗)=⌀.
( 2 ) For each Sη,θ∈CVRI∗, it sets GT=Lη∥dθ and retrieves (GT,(T∗,y)) from Lf. Then it chooses random values t,t1∈Zp and computes a time-constrained update key by implicitly setting fGTT∗=y as (29)tukT,Sη,θ=U0=gywt,U1=gt,U2=gt1,U3=uT∗ht1v-t.
( 3 ) Finally, it outputs the updated state Λ and an update key (30)ukT,R=CVRI,tukT,Sη,θSη,θ∈CVRI.
Challenge: The adversary A submits a pair of messages (m0,m1) with the same length to the simulator S. Then S flips a random bit c∈0,1 and constructs: key=F·eg,gsα1, C0=gs, where F is the challenge term and gs is the appropriate term of the assumption.
S implicitly sets a vector y=(s,sa+y2,…,saq+1yn), where y2,…,yn are chosen uniformly at random from Zp. Therefore, the secret s and the vector y are uniformly distributed. Especially s is hidden for A from information theory. Let λ=A∗yT. For each row τ∈l, it implicitly sets(31)λτ=∑i∈nAτ,i∗sai-1+∑i∈nAτ,i∗yi=∑i∈nAτ,i∗sai-1+λτ′.Let the terms λτ′ be known to S. For each row of Aτ∗, S implicitly sets tτ=-sbτ. Since bτ’s are hidden for A from information theory, the terms tτ are uniformly distributed as well. S also picks random values x1,τ′,x2,τ′,x3,τ′∈Zp and implicitly sets x1,τ=λτ-x1,τ′, x2,τ=ρ(τ)∗-x2,τ′·bτ-1, and x3,τ=-sbτ. As a result, A computes(32)C1,τ=wx1,τvx3,τ=wλτgsbτ-v1w-x1,τ′∏j,k∈l+1,n∧j≠τgsakbτbj-1-Aj,k∗∗,(33)C2,τ=ux2,τh-x3,τ=u-x2,τ′gsbτ-u1ρ∗∗τ+h1∏j,k∈l,n∧j≠τgsakbτbj-2-Aj,k∗∗ρ∗∗τ-ρ∗∗j,(34)C3,τ=gx3,τ=g-sbτ,C4,τ=λτ-x1,τ=x1,τ′,C5,τ=-x3,τρ∗∗τ-x2,τ=x2,τ′,For τ=l+1, S implicitly sets tl+1=-sbl+1 and also picks random values x1,l+1′,x2,l+1′∈Zp and implicitly sets x1,l+1=s-x1,l+1′, x2,l+1=T∗-x2,l+1′, and x3,l+1=-sbl+1. As a result, A computes(35)C1,l+1=wx1,l+1vx3,l+1=gsbl+1-v1∏j,k∈l+1,n∧j≠τgsakbl+1bj-1-Aj,k∗∗,(36)C2,l+1=ux2,l+1h-x3,l+1=gsbl+1-u1T∗+h1∏j,k∈l+1,ngsakbl+1bj-2-Aj,k∗∗T∗-ρ∗∗j,(37)C3,l+1=gx3,l+1=g-sbl+1,C4,l+1=s-x1,l+1=x1,l+1′,(38)C5,l+1=-x3,l+1T∗-x2,l+1=x2,l+1′,K′=Hkey,C3,1,C3,2,…,C3,l+1.Finally, S submits the ciphertext CT∗={A∗,ρ∗,T∗,C0=mc⊕K′, C1,τ,C2,τ,C3,τ,C4,τ,C5,ττ∈[l+1]} to A.
Phase 2: it is the same as Phase 1.
Guess: A outputs a guess c′ for the challenge ciphertext CT∗. If c′=c, S outputs 0, it means that the challenge term is F=eg,g-saq+1. Otherwise, it outputs 1.
IfF=eg,g-saq+1, A played the real security game, since key=F·eg,gαs, K′=H(key,C3,1,C3,2,…,C3,l+1), and C0=mc⊕K′. Otherwise, if F is a random value of GT, then the advantage of A is 0. Therefore, if A wins the above security game with a nonnegligible advantage, then S can solve theq-type assumption with a nonnegligible advantage by using the given terms of theq- type assumption.


## 5. Performance Analysis

This section elaborates the comparisons between our R-CP-ABOOE and some related ABE schemes on the functionalities and efficiency respects. We summarized the comparison results in Table1, where mc, M and E, respectively, denote a modular operation in Zp, a multiplication, and an exponentiation in the groups G or GT. Let l be the number of rows in the matrix A and r be the number of revoked users in R. Let ω, N, U, G, GT, and M represent the number of attributes in the collection ω, the total number of users, the number of all attributes, the size of an element in G, the size of an element in GT, and the size of a message in the space M, respectively.Table 1
Comparisons of the related attribute-based encryption schemes.
Schemes Online-Enc cost Key-update cost Ciphertext size Update-key size Rev [5] ( ω + 2 ) E r log ⁡ ( N / r ) E ω + 1 G + G T r log ⁡ ( N / r ) G √ [17] ( 2 l + r log ⁡ ( N / r ) + 3 ) E - 2 + r log ⁡ N / r + l G + G T - √ [32] ( 8 0 ω + 16 0 r - 48 ) E - 16 ω + 6 4 r - 27 G + G T - √ [9] 3 l m c - ( 3 l + 1 ) | G | + 2 l Z p + M - × Ours 3 l + 2 m c (14r-7)E 3 l + 4 G + 2 1 + l Z p + M 8 r - 4 G √In Table1, the revocable ABE schemes [5, 17, 32] and our R-CP-ABOOE scheme support user revocation. However, the real (online) encryption algorithms in the schemes [5, 17, 32] must perform many exponentiation operations, which is unsuitable for mobile devices with limited-computation power. Fortunately, in our scheme, first the offline-encryption phase can be executed by high performance computer in a trusted environment. Then our real (or online) encryption only requires 3l+2 modular operations and does not require any exponentiation. Modular operation is much faster than the exponentiation operation. Thus, our real encryption algorithm is the fastest among these schemes [5, 17, 32].In addition, compared with the indirectly revocable ABE [5], our scheme may significantly reduce the key-update cost and the size of update key from O(rlog⁡(N/r) to O(r), which is important since the update keys should be periodically broadcasted to all nonrevoked users. Compared with the directly revocable ABE [17, 32] that cannot be integrated with the online/offline technology, our encryption algorithm and ciphertext size are not related to the number of revoked users. Therefore, our scheme has less encryption overhead and shorter ciphertext length than the directly revocable ABE [17, 32], which is suitable for data owners with resource-limited devices. Although our scheme need store additional update key and small amount of offline ciphertexts, current mobile devices are perfectly capable. The online/offline ABE scheme [9] cannot provide the user revocation, whereas our scheme achieves the user revocation mechanism without excessive computational and storage costs. In general, our R-CP-ABOOE scheme is the first CP-ABE scheme, which can simultaneously support the user revocation and the online/offline encryption mode, and it has desirable features of very little encryption overhead for mobile device and less the number of group elements in a ciphertext and update key. Performance analysis shows that our scheme greatly improves the key-update efficiency for the trusted party and the encryption efficiency for mobile devices.


## 6. Conclusions

In this work, we deal with the key-update efficiency and the encryption efficiency issues in revocable CP-ABE systems and propose an efficient ciphertext-policy attribute-based online/offline encryption with user revocation (R-CP-ABOOE), which is proven to be selectively secure under theq-type assumption. Our R-CP-ABOOE scheme simultaneously supports user revocation and online/offline encryption mode and significantly improves the key-update efficiency from O(rlog⁡(N/r) to O(r). Moreover, our scheme has desirable features of very little encryption overhead for mobile device and less group elements in the update key. Performance analysis shows that our scheme greatly improves the key-update efficiency for the trusted party and the encryption efficiency for mobile devices. Furthermore, we can employ the outsourcing decryption technology [10, 16, 33] to reduce the decryption cost.



---

*Source: 8093578-2019-02-14.xml*