# A New User Revocable Ciphertext-Policy Attribute-Based Encryption with Ciphertext Update

Authors: Zhe Liu; Fuqun Wang; Kefei Chen; Fei Tang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

The revocable ciphertext-policy attribute-based encryption (R-CP-ABE) is an extension of ciphertext-policy attribute-based encryption (CP-ABE), which can realize user direct revocation and maintain a short revocation list. However, the revoked users can still decrypt the previously authorized encrypted data with their old key. The R-CP-ABE scheme should provide a mechanism to protect the encrypted data confidentiality by disqualifying the revoked users from accessing the previously encrypted data. Motivated by practical needs, we propose a new user R-CP-ABE scheme that simultaneously supports user direct revocation, short revocation list, and ciphertext update by incorporating the identity-based and time-based revocable technique. The scheme provides a strongly selective security proof under the modified decisionalq-parallel bilinear Diffie–Hellman Exponent problem, where “strongly” means that the adversary can query the secret key of a user whose attribute set satisfies the challenge ciphertext access structure and whose identity is in the revocation list.


---

## Body

## 1. Introduction

As a special kind of public key encryption (PKE), attribute-based encryption (ABE) is a one-to-many cryptographic primitive that can offer a fine-grained access control. In general, there are two types of ABE schemes, key-policy attribute-based encryption (KP-ABE) [1–4] and ciphertext-policy attribute-based encryption (CP-ABE) [5–8]. In the KP-ABE scheme, secret key is associated with an access structure, and ciphertext is labeled with a set of attributes. While in the CP-ABE scheme, secret key is related to a set of attributes, and ciphertext is associated with an access structure. Compared with the traditional method of access control system, ABE has many advantages so that it satisfies many applications for network such as cloud storage systems [9–12] and medical e-healthcare systems [13–18].However, providing an efficient and practical revocation mechanism is very important in ABE since it can prevent a user from accessing encrypted data in cryptosystems by revoking the access authority. There are mainly two methods to revoke users in ABE, namely, direct revocation and indirect revocation. The indirect revocation [19, 20] requires an authority to update key only for the nonrevoked users so that they can continue to decrypt the encrypted data. The revoked users cannot decrypt any newly generated ciphertext since their keys were not updated. However, we cannot implement user instant revocation by using this approach. Suppose an employee’s access to the encrypted data is revoked some day before the key update time, he could still decrypt any newly generated encrypted data until the key is updated. If we update the key as soon as a user is revoked to realize user instant revocation, it will be a bottleneck and not practical for a large organization where there may be an army of revoked users. Moreover, the revoked users can still have access to the previously generated encrypted data. The direct revocation [21, 22] allows a public revocation list to be specified directly during encryption so that the ciphertext cannot be decrypted by those users who are in the revocation list even if their attributes/policies satisfy the policies/attributes related to the ciphertext. Ciphertext can only be decrypted by users who are not in the revocation list and whose attributes satisfy the access policy. This method can implement user instant revocation and does not need to update the secret key, while the disadvantage is that the revocation list gets longer over time. It will be inefficient for encryption and decryption, especially for a large system.


### 1.1. Related Work

Many schemes [23–28] are presented to deal with the revocation in attribute-based access control. Boldyreva et al. in [19] proposed a revocable KP-ABE. In their scheme, the authority stores a revocation list and executes key update algorithm for the nonrevoked users who are not in the revocation list. Using the key update approach, Yu et al. in [25] put forward a revocable CP-ABE. The revoked users cannot decrypt the updated ciphertext, but access policies rarely support logical AND in their contribution. In 2012, Sahai et al. in [20] proposed a concept of revocable-storage ABE. In the scheme, they added a ciphertext delegation and ciphertext updating algorithm so that ciphertext can be decrypted only if the encryption time t<t′, where t′ is the key expiry time. In detail, the third party server can update stored ciphertext without any interaction with data owners as long as the revocation event happens and the re-encrypted ciphertext cannot be recovered by the revoked users any longer. Using the direct revocation, Balu et al. in [26] put forward a revocable CP-ABE. Their model, however, is weak that the adversary can only query the secret key of a user whose attribute set does not satisfy the challenge ciphertext access policy and whose identity is not in the revocation list.Wang et al. in [23] proposed a new revocable CP-ABE that incorporates ID-based revocation ability. In their security definition, the adversary can query the secret key of a user whose attribute set satisfies the challenge ciphertext access structure and whose identity is in the revocation list. Nevertheless, the size of the ciphertext is linear with the number of users in the revocation list, which gets longer as time goes by. Liu et al. in [29] proposed a revocable CP-ABE by using direct approach. They put forward a secret key time validation technique to address the issue of growth of the revocation list. Users can decrypt the ciphertext if and only if the validity time period of the secret key completely covers the validity time period of the ciphertext. The size of the ciphertext is only related to the embedded policy, while the size of the secret key is not only linear with the maximum length of the revocation list but also the number of attributes of the user. Their scheme can implement user direct revocation and maintain a short revocation list. However, the revoked users can still decrypt the previously authorized ciphertext with their old key. We take this issue into account where users’ access authority changes with time and ciphertext is stored by a third party.


### 1.2. Our Contribution

We propose a R-CP-ABE scheme that can implement user direct revocation, maintain a short revocation list, and update ciphertext by incorporating the identity-based and time-based revocable technique. The main contributions of this paper can be summarised as follows:(1)
User direct revocation. We have a public revocation list that contains the identity of a user who is revoked before the intended expiry time. This revocation list is embedded into the ciphertext by the encryptor to achieve user direct revocation. Users in the revocation list cannot decrypt any newly generated ciphertext even if their attribute set satisfies the access policy.(2)
Short revocation list. Once the validity time expires, the users’ keys become invalid as they are unable to decrypt any newly generated ciphertext. The revoked users whose keys are expired can be removed from the revocation list after the expiry date of their keys. Therefore, we can maintain a short revocation list.(3)
Ciphertext update. In the scheme, the ciphertext can be updated periodically using only publicly available information, and after the update process, all stored encrypted data (no matter how old) become inaccessible to the revoked users.(4)
Strongly selective security. Our scheme provides a strongly selective security proof under the modified decisional q-parallel bilinear Diffie–Hellman Exponent problem, where “strongly” means that the adversary can query the secret key of a user whose attribute set satisfies the challenge ciphertext access structure and whose identity is in the revocation list.


## 1.1. Related Work

Many schemes [23–28] are presented to deal with the revocation in attribute-based access control. Boldyreva et al. in [19] proposed a revocable KP-ABE. In their scheme, the authority stores a revocation list and executes key update algorithm for the nonrevoked users who are not in the revocation list. Using the key update approach, Yu et al. in [25] put forward a revocable CP-ABE. The revoked users cannot decrypt the updated ciphertext, but access policies rarely support logical AND in their contribution. In 2012, Sahai et al. in [20] proposed a concept of revocable-storage ABE. In the scheme, they added a ciphertext delegation and ciphertext updating algorithm so that ciphertext can be decrypted only if the encryption time t<t′, where t′ is the key expiry time. In detail, the third party server can update stored ciphertext without any interaction with data owners as long as the revocation event happens and the re-encrypted ciphertext cannot be recovered by the revoked users any longer. Using the direct revocation, Balu et al. in [26] put forward a revocable CP-ABE. Their model, however, is weak that the adversary can only query the secret key of a user whose attribute set does not satisfy the challenge ciphertext access policy and whose identity is not in the revocation list.Wang et al. in [23] proposed a new revocable CP-ABE that incorporates ID-based revocation ability. In their security definition, the adversary can query the secret key of a user whose attribute set satisfies the challenge ciphertext access structure and whose identity is in the revocation list. Nevertheless, the size of the ciphertext is linear with the number of users in the revocation list, which gets longer as time goes by. Liu et al. in [29] proposed a revocable CP-ABE by using direct approach. They put forward a secret key time validation technique to address the issue of growth of the revocation list. Users can decrypt the ciphertext if and only if the validity time period of the secret key completely covers the validity time period of the ciphertext. The size of the ciphertext is only related to the embedded policy, while the size of the secret key is not only linear with the maximum length of the revocation list but also the number of attributes of the user. Their scheme can implement user direct revocation and maintain a short revocation list. However, the revoked users can still decrypt the previously authorized ciphertext with their old key. We take this issue into account where users’ access authority changes with time and ciphertext is stored by a third party.


## 1.2. Our Contribution

We propose a R-CP-ABE scheme that can implement user direct revocation, maintain a short revocation list, and update ciphertext by incorporating the identity-based and time-based revocable technique. The main contributions of this paper can be summarised as follows:(1)
User direct revocation. We have a public revocation list that contains the identity of a user who is revoked before the intended expiry time. This revocation list is embedded into the ciphertext by the encryptor to achieve user direct revocation. Users in the revocation list cannot decrypt any newly generated ciphertext even if their attribute set satisfies the access policy.(2)
Short revocation list. Once the validity time expires, the users’ keys become invalid as they are unable to decrypt any newly generated ciphertext. The revoked users whose keys are expired can be removed from the revocation list after the expiry date of their keys. Therefore, we can maintain a short revocation list.(3)
Ciphertext update. In the scheme, the ciphertext can be updated periodically using only publicly available information, and after the update process, all stored encrypted data (no matter how old) become inaccessible to the revoked users.(4)
Strongly selective security. Our scheme provides a strongly selective security proof under the modified decisional q-parallel bilinear Diffie–Hellman Exponent problem, where “strongly” means that the adversary can query the secret key of a user whose attribute set satisfies the challenge ciphertext access structure and whose identity is in the revocation list.


## 2. Preliminaries

### 2.1. Bilinear Pairings

LetG1 and G2 be two cyclic multiplicative groups of prime order p, and g be a generator of G1. A bilinear map is a function e:G1×G1⟶G2 with the following properties:(i)
Bilinearity:eaP,bQ=eP,Qab for all P,Q∈G1 and all a,b∈ℤp(ii)
Nondegeneracy:eg,g≠1(iii)
Computability: there is a polynomial time algorithm to computeeP,Q for any P,Q∈G1


### 2.2. Access Structure

Let a set of parties beP1,P2,…,Pn. A collection A⊆2P1,P2,…,Pn is monotone if ∀B,C. If B∈A and B⊆C, then C∈A. An access structure A is a collection of nonempty subsets of P1,P2,…,Pn, i.e., A⊆2P1,P2,…,Pn\∅. For an access structure A, the sets in A are defined as authorized sets. Otherwise, the sets are defined as unauthorized sets.


### 2.3. Linear Secret-Sharing Schemes (LSSS)

An LSSS can represent an access control policyM,ρ, where M with l rows and n columns is called the share-generating matrix and the function ρ defines the party labeling row i as ρi for all i=1,…,l. A secret-sharing scheme Π over a set of parties is linear over ℤp if satisfies the following two conditions:(i)
The shares of each parties form a vector overℤp.(ii)
The column vectorv=s,r2,r3,…,rn is the secret to be shared, where s∈ℤp and r2,r3,…,rn∈ℤp are chosen randomly. According to Π, Mv is the vector of l shares of the secret s and the share Mvi belongs to party ρi.Our definition is adopted from [30], and it showed that every linear secret-sharing scheme enjoys the linear reconstruction property:(i)
Suppose thatΠ is an LSSS for the access structure A. Let any authorized set S∈A and I=i:ρi∈S⊂1,…,l. Then, there exist constants ωi∈ℤpi∈I such that ∑i∈Iωiλi=s for valid shares λi of any secret s, and we can find these constants ωi in polynomial time.We use the convention that the vector1,0,0,…,0 is the target vector for any linear secret-sharing scheme. The target vector 1,0,0,…,0 is in the span of I for any satisfying set of rows I in M. For any unauthorized set of rows I, the target vector is not in the span of I. A vector w exists such that w⋅1,0,0,…,0=−1.


### 2.4. Security Assumption

The modified decisionalq-parallel bilinear Diffie–Hellman Exponent problem (M-q-parallel-BDHE) is defined as follows. Given(1)y=g,gs,ga,…,gaq,gaq+2,…,ga2q,∀1≤j≤qga/bj,…,gaq/bj,gaq+2/bj,…,ga2q/bj,∀1≤j≤qga⋅s/bj,…,gaq⋅s/bj,where G1 is a group of prime order p with a random generator g and the random exponents a,s,b1,b2,…,bq∈ℤp, in order to distinguish eg,gaq+1s∈G2 from a random element R∈G2.The advantage of solving the M-q-parallel-BDHE problem in G1 with algorithm ℬ is ε if the following equation holds:(2)Prℬy,T=eg,gaq+1s=0−Prℬy,T=R=0≥ε.The M-q-parallel-BDHE assumption holds if the advantage ε of any probabilistic polynomial time (PPT) algorithm to solve the M-q-parallel-BDHE problem is a negligible function of the security parameter.


## 2.1. Bilinear Pairings

LetG1 and G2 be two cyclic multiplicative groups of prime order p, and g be a generator of G1. A bilinear map is a function e:G1×G1⟶G2 with the following properties:(i)
Bilinearity:eaP,bQ=eP,Qab for all P,Q∈G1 and all a,b∈ℤp(ii)
Nondegeneracy:eg,g≠1(iii)
Computability: there is a polynomial time algorithm to computeeP,Q for any P,Q∈G1


## 2.2. Access Structure

Let a set of parties beP1,P2,…,Pn. A collection A⊆2P1,P2,…,Pn is monotone if ∀B,C. If B∈A and B⊆C, then C∈A. An access structure A is a collection of nonempty subsets of P1,P2,…,Pn, i.e., A⊆2P1,P2,…,Pn\∅. For an access structure A, the sets in A are defined as authorized sets. Otherwise, the sets are defined as unauthorized sets.


## 2.3. Linear Secret-Sharing Schemes (LSSS)

An LSSS can represent an access control policyM,ρ, where M with l rows and n columns is called the share-generating matrix and the function ρ defines the party labeling row i as ρi for all i=1,…,l. A secret-sharing scheme Π over a set of parties is linear over ℤp if satisfies the following two conditions:(i)
The shares of each parties form a vector overℤp.(ii)
The column vectorv=s,r2,r3,…,rn is the secret to be shared, where s∈ℤp and r2,r3,…,rn∈ℤp are chosen randomly. According to Π, Mv is the vector of l shares of the secret s and the share Mvi belongs to party ρi.Our definition is adopted from [30], and it showed that every linear secret-sharing scheme enjoys the linear reconstruction property:(i)
Suppose thatΠ is an LSSS for the access structure A. Let any authorized set S∈A and I=i:ρi∈S⊂1,…,l. Then, there exist constants ωi∈ℤpi∈I such that ∑i∈Iωiλi=s for valid shares λi of any secret s, and we can find these constants ωi in polynomial time.We use the convention that the vector1,0,0,…,0 is the target vector for any linear secret-sharing scheme. The target vector 1,0,0,…,0 is in the span of I for any satisfying set of rows I in M. For any unauthorized set of rows I, the target vector is not in the span of I. A vector w exists such that w⋅1,0,0,…,0=−1.


## 2.4. Security Assumption

The modified decisionalq-parallel bilinear Diffie–Hellman Exponent problem (M-q-parallel-BDHE) is defined as follows. Given(1)y=g,gs,ga,…,gaq,gaq+2,…,ga2q,∀1≤j≤qga/bj,…,gaq/bj,gaq+2/bj,…,ga2q/bj,∀1≤j≤qga⋅s/bj,…,gaq⋅s/bj,where G1 is a group of prime order p with a random generator g and the random exponents a,s,b1,b2,…,bq∈ℤp, in order to distinguish eg,gaq+1s∈G2 from a random element R∈G2.The advantage of solving the M-q-parallel-BDHE problem in G1 with algorithm ℬ is ε if the following equation holds:(2)Prℬy,T=eg,gaq+1s=0−Prℬy,T=R=0≥ε.The M-q-parallel-BDHE assumption holds if the advantage ε of any probabilistic polynomial time (PPT) algorithm to solve the M-q-parallel-BDHE problem is a negligible function of the security parameter.


## 3. Definition

### 3.1. Time Period

Similar to the definition of time period in [29], our time period is hierarchical that we use a hierarchical tree to represent the time period for year, month, and day. Let T be the depth of the hierarchical tree, the first level represents the year, the second level represents the month, and the third level represents the day. Every node has z children, and each node (except the root node) represents a time period in the tree. We assume that all users agree on how to divide time and how to specify each time period. A time period τ=τ1,τ2,…,τk, where the j-th component corresponds to the time period at level j. For example, we use 2020.08.22 to represent a day, 2020.08 to represent a month and so on.A secret key validity time for a user is a time period from a starting date to an ending date. For example, a user joins the organization on 2019.12.30 and ends on 2020.12.31, and then his secret key validity time is from 2019.12.30 to 2020.12.31. A decryptable time period is a time period set by the encryptor so that only users with validity time completely covers the period can decrypt. For example, suppose the decryptable time period is 2019.12 and the secret key validity of a user is only limited to 2019.12.31. This secret key is unable to decrypt as it does not have a complete cover for the decryptable time period. However, if the decryptable time period is 2019.12.31 and the secret key validity of a user is 2019.12, then it is able to decrypt as it has a complete cover for the decryptable time period.


### 3.2. Algorithms of R-CP-ABE

The R-CP-ABE scheme consists of five PPT algorithms:Setup, KeyGen, Encrypt, Decrypt, and CTUpdate:(i)
Setupλ,U,T,I: the setup algorithm takes as input the security parameter λ, the number of attributes in the system U, the depth of the time tree T, and the identity set I. It outputs the public parameters PK and a master key MK.(ii)
KeyGenMK,ID,S,T: the key generation algorithm takes as input the master key MK, a user’s ID, a set of attributes S, and a range of time periods T for the user’s ID. It outputs a private key SKID,S,T.(iii)
EncryptPK,ℳ,Tc,ℛ,A=M,ρ: the encryption algorithm takes as input the public parameters PK, a message ℳ, a decryptable time period Tc, a revoked set ℛ, and an access structure A over the universe of attributes. It outputs a ciphertext CT.(iv)
DecryptCT,ℛ,A,Tc,SKID,S,T: the decryption algorithm takes as input a ciphertext CT, with a description of a revoked set ℛ, an access structure A and the time periods Tc, and a private key SKID,S,T. If and only if the user’s identity ID is not in the revocation list, the set S of attributes satisfies the access structure A associated with CT and the range of validity time periods T completely covering the decryptable time periods Tc, and then it outputs the message ℳ.(v)
CTUpdatePK,CT,ℛ′,Tc,A=M,ρ: the ciphertext update algorithm takes as input the public parameters PK, the ciphertext CT, a new revoked set ℛ′, the decryptable time period Tc, and an access structure A=M,ρ. It outputs a new ciphertext CT′.Note that compared to the algorithms of R-CP-ABE scheme [29], we add a ciphertext update algorithm to prevent the revoked users from accessing the previously authorized encrypted data. We do not explicitly propose a key update algorithm as its function can be covered by the KeyGen algorithm. We run the KeyGen algorithm to generate a new secret key with a new time period for the nonrevoked users during a reasonable period (e.g., employees that renew their contracts when they expire).


### 3.3. Security Model

Due to the updated ciphertext has the same distribution as the original ciphertext, we only consider the security of the original ciphertext. The security model is described by the following a game between a challengerC and an adversary A. In the game, A needs to submit an access structure A∗, a revocation list ℛ∗, and a decryptable time period Tc∗ to C before seeing the public parameters PK. A can query any private key at any time that cannot be used to decrypt the challenge ciphertext, which derives from the security definitions for identity-based revocation framework in [31] and general CP-ABE systems in [7]. In the security definition, we consider a strong adversary who can query the secret key of a user whose attribute set satisfies the challenge ciphertext access structure and whose identity is in the revocation list.(i)
Init: the adversary A submits the challenge access structure A∗, the challenge revocation list ℛ∗, and the challenge decryptable time period Tc∗ to the challenger C.(ii)
Setup: C launches the Setup algorithm to generate the system parameters. It keeps the master key MK and sends the public parameters PK to A.(iii)
Phase1:A makes private key queries repeatedly corresponding to the identity ID, the attribute set S, and the range of time periods T such that, for any single returned secret key SKID,S,T, at least one of the following requirements is satisfied:(i)
S satisfies the access structure A∗ and the corresponding identity ID∈ℛ∗(ii)
Tc∗ is not completely covered in T(iv)
Challenge: A submits two equal length messages ℳ0 and ℳ1 to C. And then, C flips a random coin b∈0,1 and encrypts ℳb under the access structure A∗, the revoked set ℛ∗, and the time period Tc∗ to obtain a ciphertext CT∗. Finally, C sends the ciphertext CT∗ to A.(v)
Phase2: this phase is completely same as the Phase 1.(vi)
Guess: A outputs a guess b′ of b.The advantage ofA winning the game is defined as AdvA=Prb′=b−1/2.(i)
Definition: if no adversary has a nonnegligible advantage to win the above game in polynomial time, then the revocable ciphertext-policy attribute-based encryption scheme is secure.


## 3.1. Time Period

Similar to the definition of time period in [29], our time period is hierarchical that we use a hierarchical tree to represent the time period for year, month, and day. Let T be the depth of the hierarchical tree, the first level represents the year, the second level represents the month, and the third level represents the day. Every node has z children, and each node (except the root node) represents a time period in the tree. We assume that all users agree on how to divide time and how to specify each time period. A time period τ=τ1,τ2,…,τk, where the j-th component corresponds to the time period at level j. For example, we use 2020.08.22 to represent a day, 2020.08 to represent a month and so on.A secret key validity time for a user is a time period from a starting date to an ending date. For example, a user joins the organization on 2019.12.30 and ends on 2020.12.31, and then his secret key validity time is from 2019.12.30 to 2020.12.31. A decryptable time period is a time period set by the encryptor so that only users with validity time completely covers the period can decrypt. For example, suppose the decryptable time period is 2019.12 and the secret key validity of a user is only limited to 2019.12.31. This secret key is unable to decrypt as it does not have a complete cover for the decryptable time period. However, if the decryptable time period is 2019.12.31 and the secret key validity of a user is 2019.12, then it is able to decrypt as it has a complete cover for the decryptable time period.


## 3.2. Algorithms of R-CP-ABE

The R-CP-ABE scheme consists of five PPT algorithms:Setup, KeyGen, Encrypt, Decrypt, and CTUpdate:(i)
Setupλ,U,T,I: the setup algorithm takes as input the security parameter λ, the number of attributes in the system U, the depth of the time tree T, and the identity set I. It outputs the public parameters PK and a master key MK.(ii)
KeyGenMK,ID,S,T: the key generation algorithm takes as input the master key MK, a user’s ID, a set of attributes S, and a range of time periods T for the user’s ID. It outputs a private key SKID,S,T.(iii)
EncryptPK,ℳ,Tc,ℛ,A=M,ρ: the encryption algorithm takes as input the public parameters PK, a message ℳ, a decryptable time period Tc, a revoked set ℛ, and an access structure A over the universe of attributes. It outputs a ciphertext CT.(iv)
DecryptCT,ℛ,A,Tc,SKID,S,T: the decryption algorithm takes as input a ciphertext CT, with a description of a revoked set ℛ, an access structure A and the time periods Tc, and a private key SKID,S,T. If and only if the user’s identity ID is not in the revocation list, the set S of attributes satisfies the access structure A associated with CT and the range of validity time periods T completely covering the decryptable time periods Tc, and then it outputs the message ℳ.(v)
CTUpdatePK,CT,ℛ′,Tc,A=M,ρ: the ciphertext update algorithm takes as input the public parameters PK, the ciphertext CT, a new revoked set ℛ′, the decryptable time period Tc, and an access structure A=M,ρ. It outputs a new ciphertext CT′.Note that compared to the algorithms of R-CP-ABE scheme [29], we add a ciphertext update algorithm to prevent the revoked users from accessing the previously authorized encrypted data. We do not explicitly propose a key update algorithm as its function can be covered by the KeyGen algorithm. We run the KeyGen algorithm to generate a new secret key with a new time period for the nonrevoked users during a reasonable period (e.g., employees that renew their contracts when they expire).


## 3.3. Security Model

Due to the updated ciphertext has the same distribution as the original ciphertext, we only consider the security of the original ciphertext. The security model is described by the following a game between a challengerC and an adversary A. In the game, A needs to submit an access structure A∗, a revocation list ℛ∗, and a decryptable time period Tc∗ to C before seeing the public parameters PK. A can query any private key at any time that cannot be used to decrypt the challenge ciphertext, which derives from the security definitions for identity-based revocation framework in [31] and general CP-ABE systems in [7]. In the security definition, we consider a strong adversary who can query the secret key of a user whose attribute set satisfies the challenge ciphertext access structure and whose identity is in the revocation list.(i)
Init: the adversary A submits the challenge access structure A∗, the challenge revocation list ℛ∗, and the challenge decryptable time period Tc∗ to the challenger C.(ii)
Setup: C launches the Setup algorithm to generate the system parameters. It keeps the master key MK and sends the public parameters PK to A.(iii)
Phase1:A makes private key queries repeatedly corresponding to the identity ID, the attribute set S, and the range of time periods T such that, for any single returned secret key SKID,S,T, at least one of the following requirements is satisfied:(i)
S satisfies the access structure A∗ and the corresponding identity ID∈ℛ∗(ii)
Tc∗ is not completely covered in T(iv)
Challenge: A submits two equal length messages ℳ0 and ℳ1 to C. And then, C flips a random coin b∈0,1 and encrypts ℳb under the access structure A∗, the revoked set ℛ∗, and the time period Tc∗ to obtain a ciphertext CT∗. Finally, C sends the ciphertext CT∗ to A.(v)
Phase2: this phase is completely same as the Phase 1.(vi)
Guess: A outputs a guess b′ of b.The advantage ofA winning the game is defined as AdvA=Prb′=b−1/2.(i)
Definition: if no adversary has a nonnegligible advantage to win the above game in polynomial time, then the revocable ciphertext-policy attribute-based encryption scheme is secure.


## 4. Our Scheme

### 4.1. Overview

Based on the scheme [23] and the secret key time validation technique in [29], we propose the R-CP-ABE scheme with ciphertext update. We incorporate identity and time period to the generating process of the secret key. The size of the revocation list can be reduced by incorporating validity time period technique. The identity of a user who is revoked before his intended expiry date is embedded into the revocation list by the encryptor to realize user direct revocation. Users in the revocation list cannot decrypt any newly encrypted data. In order to disqualify the revoked users from accessing the previously encrypted data, we provide a ciphertext update mechanism. Finally, our scheme can implement user direct revocation, maintain a short revocation list, and update ciphertext.


### 4.2. Technique Construction

Similar to the validity time technique in [29] from the hierarchical IBE (HIBE) scheme [13], we represent time period by using a hierarchical tree, which can shorten the size of the secret key. In this hierarchical tree, each node has a corresponding time period associated with the secret key, and the secret key of any node can derive the secret key for children of that node. For example, a user with secret key validity time period for the whole year can derive the key with validity time period for the underlying months of that year.We select the minimum number of nodes that can represent all the validity time periods by using the set-cover approach. Suppose a user joins the organization on 2019.12.30 and ends on 2020.12.31, then his secret key validity time is from 2019.12.30 to 2020.12.31. He should obtain secret key from the nodes of2019.12.30,2019.12.31, and 2020 by using the set-cover approach. Then, the secret time period is the set 2019.12.30,2019.12.31,2020.The detailed construction of the scheme is as follows:(i)
SetupU,T,I: U is the number of attributes in the system. The time periods are represented as a z-ary string 1,zT−1. I is the identity set. The algorithm chooses a bilinear group G1 of prime order p with a random generator g and U random group elements h1,h2,…,hU∈G1. It also randomly chooses α,b∈ℤp and V0,V1,…,VT∈G1. It outputs:(3)PK=g,gb,gb2,eg,gα,h1b,…,hUb,V0,V1,…,VT,andMK=α,b.(ii)
KeyGenMK,ID,S,T: S is the set of attributes of a user with identity ID∈I. T is the time period for the user ID. T is denoted as the set-cover to represent T which consists of some time elements τ=τ1,τ2,…,τkτ∈1,zkτ for any τ∈T. The algorithm randomly chooses t, vτ∈ℤp for any τ∈T and computes(4)D0=gt,D0,τ=gvττ∈T,D1,τ=gαgb2tV0∏j=1kτVjτjvττ∈T,Lj,τ=Vjτjj=kτ+1,…T,τ∈T,Kx=gb⋅IDhx−tx∈S.Then, the secret key is(5)SKID,S,T=D0,D0,τ,D1,τ,Lkτ+1,τ,…,LT,ττ∈T,Kxx∈S.(iii)
EncryptPK,ℳ,Tc,ℛ,A=M,ρ: the revocation list ℛ=ID1,…,IDr with r revoked users. The message ℳ∈G2 and the decryptable time period of the ciphertext is Tc. τc=τ1,τ2,…,τk∈1,zk denotes the representation of Tc. It takes as input an LSSS access structure A=M,ρ, where M is an l×n matrix and ρ is a function maps rows of M into attributes. The encryption algorithm chooses a random vector v=s,y2,…,yn∈ℤpn to share the encryption exponent s. For i=1,…,l, it calculates λi=v⋅Mi, where the vector Mi corresponds to the i-th row of M. Let IDj denote the j-th identity in ℛ. The algorithm also chooses random μ1,…,μr∈ℤp such that μ = μ1+μ2+⋯+μr. It computes(6)C0=ℳ⋅eg,gαsμ,C0′=gsμ,C0″=V0∏j=1kVjτjsμ,Ci,j=gbλiμj,Ci,j′=gb2IDjhρibλiμj.Then,CT=C0,C0′,C0″,Ci,j,Ci,j′ along with a description of the revoked set ℛ, the access structure A=M,ρ, and the time periods Tc.(iv)
DecryptCT,ℛ,SKID,S,T: the decryption algorithm takes as input a ciphertext CT with access structure M,ρ, the revocation list ℛ, and the private key SKID,S,T. If the following requirements occurs, output ⊥:(i)
S satisfies the access structure A and the corresponding identity ID∈ℛ(ii)
Tc is not completely covered in T, that is, τc and all its prefixes are not in TOtherwise, we haveID∉ℛ, and S satisfies the access structure A=M,ρ. Define I=i:ρi∈S∈1,2,…,l. There exists a set of constants ωi∈ℤpi∈I such that ∑i∈Iωiλi=s, if λi are valid shares of any secret s according to M. It computes(7)∏i∈I∏j=1reCi,j′,D0⋅eCi,j,Kρi1/ID−IDjωi=∏i∈I∏j=1regb2λiIDjhρiλibμj,gt⋅egbλiμj,gb⋅IDhρi−t1/ID−IDjωi=∏i∈I∏j=1regb2λiIDj⋅μj,gt⋅egb2λiID⋅μj,g−t1/ID−IDjωi=∏i∈I∏j=1reg,gb2tλiμjIDj−ID1/ID−IDjωi=∏i∈I∏j=1reg,gb2tλiμj−ωi=∏i∈Ieg,g∑j=1rμjb2tλi−ωi=eg,g−b2tμ∑i∈Iλiωi=eg,g−b2tμs.DenoteA=eD1,τ,C0′. Finally, it computes(8)C0⋅eD0,τ,C0″A⋅∏i∈I∏j=1reCi,j′,D0⋅eCi,j,Kρi1/ID−IDjωi.The process is as follows:(9)C0⋅eD0,τ,C0″A⋅∏i∈I∏j=1reCi,j′,D0⋅eCi,j,Kρi1/ID−IDjωi=ℳ⋅eg,gαsμ⋅egvτ,V0∏j=1kVjτjsμegαgb2tV0∏j=1kVjτjvτ,gsμ⋅eg,g−b2tμs=ℳ⋅eg,gαsμ⋅egvτ,V0∏j=1kVjτjsμ⋅eg,gb2tμsegα,gsμ⋅egb2t,gsμ⋅eV0∏j=1kVjτjvτ,gsμ=ℳ.(v)
CTUpdatePK,CT,Tc,ℛ′,A=M,ρ: the ciphertext update algorithm takes as input the ciphertext CT, the decryptable time period Tc, and a new revocation list ℛ′ such that ℛ⊆ℛ′. Denote ℛ′=ID1,…,IDr,…,IDr+r′ with r+r′ revoked users. It takes an LSSS access structure A=M,ρ, where M is an l×n matrix and ρ is a function maps rows of M into attributes. The algorithm chooses a random vector v′=s′,y2′,…,yn′∈ℤpn to share the encryption exponent s′. For i=1,…,l, it calculates λi′=v′⋅Mi, where the vector Mi corresponds to the i-th row of M. Let IDj denote the j-th identity. It also chooses random c such that μ′=μ1′,…,μr′,…,μr+r′′∈ℤp and computes(10)C˜0=C0⋅eg,gαs′μ′=ℳeg,gαsμ+s′μ′,C˜0′=C0′⋅gs′μ′=gsμ+s′μ′,C˜0″=C0″⋅V0∏j=1kVjτjs′μ′=V0∏j=1kVjτjsμ+s′μ′,C˜i,j=Ci,j⋅gbλi′μj′=gbλiμj+λi′μj′,C˜i,j′=Ci,j′⋅gb2IDjhρibλi′μj′=gb2IDjhρibλiμj+λi′μj′.Then,CT′=C˜0,C˜0′,C0″˜,C˜i,j,C˜i,j′ along with a description of the revoked set ℛ, the access structure A=M,ρ, and the time periods Tc.


## 4.1. Overview

Based on the scheme [23] and the secret key time validation technique in [29], we propose the R-CP-ABE scheme with ciphertext update. We incorporate identity and time period to the generating process of the secret key. The size of the revocation list can be reduced by incorporating validity time period technique. The identity of a user who is revoked before his intended expiry date is embedded into the revocation list by the encryptor to realize user direct revocation. Users in the revocation list cannot decrypt any newly encrypted data. In order to disqualify the revoked users from accessing the previously encrypted data, we provide a ciphertext update mechanism. Finally, our scheme can implement user direct revocation, maintain a short revocation list, and update ciphertext.


## 4.2. Technique Construction

Similar to the validity time technique in [29] from the hierarchical IBE (HIBE) scheme [13], we represent time period by using a hierarchical tree, which can shorten the size of the secret key. In this hierarchical tree, each node has a corresponding time period associated with the secret key, and the secret key of any node can derive the secret key for children of that node. For example, a user with secret key validity time period for the whole year can derive the key with validity time period for the underlying months of that year.We select the minimum number of nodes that can represent all the validity time periods by using the set-cover approach. Suppose a user joins the organization on 2019.12.30 and ends on 2020.12.31, then his secret key validity time is from 2019.12.30 to 2020.12.31. He should obtain secret key from the nodes of2019.12.30,2019.12.31, and 2020 by using the set-cover approach. Then, the secret time period is the set 2019.12.30,2019.12.31,2020.The detailed construction of the scheme is as follows:(i)
SetupU,T,I: U is the number of attributes in the system. The time periods are represented as a z-ary string 1,zT−1. I is the identity set. The algorithm chooses a bilinear group G1 of prime order p with a random generator g and U random group elements h1,h2,…,hU∈G1. It also randomly chooses α,b∈ℤp and V0,V1,…,VT∈G1. It outputs:(3)PK=g,gb,gb2,eg,gα,h1b,…,hUb,V0,V1,…,VT,andMK=α,b.(ii)
KeyGenMK,ID,S,T: S is the set of attributes of a user with identity ID∈I. T is the time period for the user ID. T is denoted as the set-cover to represent T which consists of some time elements τ=τ1,τ2,…,τkτ∈1,zkτ for any τ∈T. The algorithm randomly chooses t, vτ∈ℤp for any τ∈T and computes(4)D0=gt,D0,τ=gvττ∈T,D1,τ=gαgb2tV0∏j=1kτVjτjvττ∈T,Lj,τ=Vjτjj=kτ+1,…T,τ∈T,Kx=gb⋅IDhx−tx∈S.Then, the secret key is(5)SKID,S,T=D0,D0,τ,D1,τ,Lkτ+1,τ,…,LT,ττ∈T,Kxx∈S.(iii)
EncryptPK,ℳ,Tc,ℛ,A=M,ρ: the revocation list ℛ=ID1,…,IDr with r revoked users. The message ℳ∈G2 and the decryptable time period of the ciphertext is Tc. τc=τ1,τ2,…,τk∈1,zk denotes the representation of Tc. It takes as input an LSSS access structure A=M,ρ, where M is an l×n matrix and ρ is a function maps rows of M into attributes. The encryption algorithm chooses a random vector v=s,y2,…,yn∈ℤpn to share the encryption exponent s. For i=1,…,l, it calculates λi=v⋅Mi, where the vector Mi corresponds to the i-th row of M. Let IDj denote the j-th identity in ℛ. The algorithm also chooses random μ1,…,μr∈ℤp such that μ = μ1+μ2+⋯+μr. It computes(6)C0=ℳ⋅eg,gαsμ,C0′=gsμ,C0″=V0∏j=1kVjτjsμ,Ci,j=gbλiμj,Ci,j′=gb2IDjhρibλiμj.Then,CT=C0,C0′,C0″,Ci,j,Ci,j′ along with a description of the revoked set ℛ, the access structure A=M,ρ, and the time periods Tc.(iv)
DecryptCT,ℛ,SKID,S,T: the decryption algorithm takes as input a ciphertext CT with access structure M,ρ, the revocation list ℛ, and the private key SKID,S,T. If the following requirements occurs, output ⊥:(i)
S satisfies the access structure A and the corresponding identity ID∈ℛ(ii)
Tc is not completely covered in T, that is, τc and all its prefixes are not in TOtherwise, we haveID∉ℛ, and S satisfies the access structure A=M,ρ. Define I=i:ρi∈S∈1,2,…,l. There exists a set of constants ωi∈ℤpi∈I such that ∑i∈Iωiλi=s, if λi are valid shares of any secret s according to M. It computes(7)∏i∈I∏j=1reCi,j′,D0⋅eCi,j,Kρi1/ID−IDjωi=∏i∈I∏j=1regb2λiIDjhρiλibμj,gt⋅egbλiμj,gb⋅IDhρi−t1/ID−IDjωi=∏i∈I∏j=1regb2λiIDj⋅μj,gt⋅egb2λiID⋅μj,g−t1/ID−IDjωi=∏i∈I∏j=1reg,gb2tλiμjIDj−ID1/ID−IDjωi=∏i∈I∏j=1reg,gb2tλiμj−ωi=∏i∈Ieg,g∑j=1rμjb2tλi−ωi=eg,g−b2tμ∑i∈Iλiωi=eg,g−b2tμs.DenoteA=eD1,τ,C0′. Finally, it computes(8)C0⋅eD0,τ,C0″A⋅∏i∈I∏j=1reCi,j′,D0⋅eCi,j,Kρi1/ID−IDjωi.The process is as follows:(9)C0⋅eD0,τ,C0″A⋅∏i∈I∏j=1reCi,j′,D0⋅eCi,j,Kρi1/ID−IDjωi=ℳ⋅eg,gαsμ⋅egvτ,V0∏j=1kVjτjsμegαgb2tV0∏j=1kVjτjvτ,gsμ⋅eg,g−b2tμs=ℳ⋅eg,gαsμ⋅egvτ,V0∏j=1kVjτjsμ⋅eg,gb2tμsegα,gsμ⋅egb2t,gsμ⋅eV0∏j=1kVjτjvτ,gsμ=ℳ.(v)
CTUpdatePK,CT,Tc,ℛ′,A=M,ρ: the ciphertext update algorithm takes as input the ciphertext CT, the decryptable time period Tc, and a new revocation list ℛ′ such that ℛ⊆ℛ′. Denote ℛ′=ID1,…,IDr,…,IDr+r′ with r+r′ revoked users. It takes an LSSS access structure A=M,ρ, where M is an l×n matrix and ρ is a function maps rows of M into attributes. The algorithm chooses a random vector v′=s′,y2′,…,yn′∈ℤpn to share the encryption exponent s′. For i=1,…,l, it calculates λi′=v′⋅Mi, where the vector Mi corresponds to the i-th row of M. Let IDj denote the j-th identity. It also chooses random c such that μ′=μ1′,…,μr′,…,μr+r′′∈ℤp and computes(10)C˜0=C0⋅eg,gαs′μ′=ℳeg,gαsμ+s′μ′,C˜0′=C0′⋅gs′μ′=gsμ+s′μ′,C˜0″=C0″⋅V0∏j=1kVjτjs′μ′=V0∏j=1kVjτjsμ+s′μ′,C˜i,j=Ci,j⋅gbλi′μj′=gbλiμj+λi′μj′,C˜i,j′=Ci,j′⋅gb2IDjhρibλi′μj′=gb2IDjhρibλiμj+λi′μj′.Then,CT′=C˜0,C˜0′,C0″˜,C˜i,j,C˜i,j′ along with a description of the revoked set ℛ, the access structure A=M,ρ, and the time periods Tc.


## 5. Security Analysis

Our construction security is based on the modified decisionalq-parallel-BDHE assumption. It is apparent that the updated ciphertext has the same distribution as the original ciphertext, so we only prove the security associated with the original ciphertext.Theorem1.
Suppose the modified decisionalq-parallel-BDHE assumption holds. Then, no PPT adversary can selectively break our system in with a challenge matrix of size l∗×n∗, where l∗,n∗<q, a challenge revocation list ℛ∗ where ℛ∗<q−2 and a challenge time Tc∗ with z-ary representation τ∗=τ1∗,…,τk∗∗ for some k∗<T such that T<q.Proof.
Suppose there is an adversaryA with nonnegligible advantage ε=AdvA against our scheme in the selective security game. Then, simulator ℬ can solve the modified decisional q-parallel-BDHE problem with nonnegligible advantage.(i)
Init: the simulator ℬ takes in a modified decisional q-parallel-BDHE problem challenge y,T:(11)y=g,gs,ga,…,gaq,gaq+2,…,ga2q,∀1≤j≤qga/bj,…,gaq/bj,gaq+2/bj,…,ga2q/bj,∀1≤j≤qga⋅s/bj,…,gaq⋅s/bj,and decides ifT = T=eg,gs⋅aq+1 using the adversary A. Then, the adversary A declares the challenge time Tc∗ with z-ary representation τ∗=τ1∗,…,τk∗∗ for some k∗≤T and the challenge revocation list ℛ∗, where ℛ∗≤q−2. A also gives the challenge access structure M∗,ρ∗ to the simulator ℬ, where M∗ is l∗×n∗. Let M∗=M1∗,M2∗,…,Ml∗∗T, where each row vector Mi∗=Mi,1∗,Mi,2∗,…,Mi,n∗∗ for 1≤i≤l∗.(ii)
Setup: the simulator ℬ chooses a random value α′ and lets eg,gα=eg,gα′ega,gaq to implicitly set α=α′+aq+1. Moreover, it also implicitly sets b=a by computing the public parameters as gb=ga,gb2=ga2. To embed the revocation identification IDc and the challenge access structure into the public parameters h1,h2,…,hU, we let the challenge matrix M∗ as a row vector set and divide it into three subsets M′,M″,M‴ such that M′∪M″∪M‴=M∗ and M′∩M″∩M‴=∅. Specially, M′,M″, and M‴ are initially set to be empty set. Define the n-dimension vectors e=1,0,…,0 and u=a2,a3,…,an+1. For i=1 to l∗, if Mi∗ is linearly independent on M′ and e cannot be linearly expressed by M′∪Mi∗, then we merge Mi∗ into M′; if Mi∗ is linearly independent on M′ and e can be linearly expressed by M′∪Mi∗, then we merge Mi∗ into M‴; if Mi∗ is dependent on M′, then we merge Mi∗ into M″. As a result, M′ is a linear independent vector group, while each vector in M″ can be linearly expressed by M′. Although e cannot be spanned by M′, it can be linearly expressed by M′ merged with each vector in M‴. Therefore, each vector in M∗ can be linearly expressed by M′∪e.
Next, we describe how the simulatorℬ programs the public parameters h1b,h2b,…,hUb. Let X denote the set of indices i, such that ρi = x. Assume that there are m vectors in M′ and let M′=M1′,M2′,…,Mm′T. For each i∈X, its corresponding row vector Mi∗ can be written as εi,0e+εi,1M1′+⋯+εi,mMm′, where εi,0,εi,1,…,εi,m∈ℤpm+1. For each Mi∗, we define a corresponding vector Mi, where Mi=εi,1M1′+⋯+εi,mMm′. As a result, we get a new vector group M′=M1,M2,…,Ml∗, and each Mi is in the span of M′. By choosing a random value zx, the simulator ℬ programs hx and hxb as(12)hx=gzx⋅g−a∑l=1rIDcl⋅∏i∈Xgεi,0e+εi,1M1′+⋯+εi,mMm′⋅u⟶/bi=gzx⋅g−a∑l=1rIDcl⋅∏i∈X∏j=1ngMi,jaj+1/bi,hxb=gzx⋅g−a2∑l=1rIDcl⋅∏i∈X∏j=1ngMi,jaj+1/bi.
IfX is an empty set, it sets hxb=gzx. And the simulator ℬ also randomly chooses ξ0,ξ1,…,ξT∈ℤp and defines Vj=gξjaq−j+1 and V0 = Vo=∏j=1k∗Vj−τj∗gξ0 for j∈1,T. Then, ℬ publishes the above parameters g,gb,gb2,h1b,…,hUb,V0,…,VT,eg,gα as the public key and sends it to A. We observe that the public parameters are distributed randomly as the real system and both the revoked identification and the challenge matrix are reflected in the simulation’s contribution of the parameter hxb.(i)
Phase1: adversary A makes repeated private keys queries corresponding to the tuple of identity, attributes, and time ID,S,T such that at least one of the following requirements is satisfied:(i)
The attributes setS∗ satisfies the access structure A∗ and the corresponding identity ID∈ℛ∗(ii)
Tc∗ and all its prefixes are not in T, the set-cover of TWe separate into two cases:(i)
Case1: the attributes set S∗ satisfies the access structure A∗ and the corresponding identity ID∈ℛ∗. Since each Mi is in the span of M1∗ and e is not in the span of M1∗, we can still find a vector ω with ω1=−1 and ω⋅Mi=0, where 1≤i≤l∗. The simulator ℬ chooses a random value r′ and computes the private key as(13)L=gr′+ω⋅v=gr′∏i=1l∗gaq−iωi,which implicitly sets the randomt as t=r′+ω⋅v=r′+ω1aq−1+ω1aq−2+⋯+ωnaq−n∗, where v=aq−1,aq−2,…,aq−n∗+2. So, it can cancel out the unknown term of the form gq+1 in gα when creating the K component in the private key as(14)K=gα′ga2r′∏i=0n−2gaq+iωi.Next, it performs this by setting(15)D0=gr′∏i=1ngaq+1−iωi=gt.In order to prevent the appearance of the term of the formgaq+1, it sets the private component Kx as(16)Kx=gzxgaID−∑m=1rIDcm⋅∏i∈XgMi⋅u⟶/bir+ω⋅v=gzxr+ω⋅vgaID−∑m=1rIDcmr+ω⋅v⋅∏i∈Xgεi,0e+εi,1M1′+⋯+εi,mMm′r+ω⋅v/bi=gzxr+ω⋅vgaID−∑m=1rIDcmr+ω⋅v⋅∏i∈XgMi,1a2+⋯+Mi,nanr/bi⋅∑i∈X∏j=1n∏k=1,k≠jngMi,jωkaq+j−k+1/bi,ℬ randomly chooses vτ∈ℤp and sets D0,τ = gvτ for all τ=τ1,…,τkτ∈T. Then, it computes(17)D1,τ=gα′gar′∏i=1n∗gaq+2−iωiV0∏j=1kτVjτjvτ=gα′gaq+1gar′g−aq+1∏i=2n∗gaq+2−iωiV0∏j=1kτVjτjvτ=gαgar′gω1⋅aq+1∏i=2n∗gaq+2−iωiV0∏j=1kτVjτjvτ=gαgr′∏i=1n∗gaq+1−iωiaV0∏j=1kτVjτjvτ=gαgatV0∏j=1kτVjτjvτ=gαgbtV0∏j=1kτVjτjvτ,ℬ also computes Lj,τ=Vjvτj=kτ+1,…,T,τ∈T.(ii)
Case2: Tc∗ and all its prefixes are not in T, the set-cover of T. For all τ=(τ=τ1,…,τkτ∈T), first define τkτ+1=⋯=τq=0 and τk∗+1∗=⋯=τq∗=0. There exists a smallest index k′≤k∗ such that τk′≠τk′∗. Simulator ℬ randomly selects vτ∈ℤp and implicitly defines vτ˜=ak′/ξk′τk′∗−τk′+vτ. It performs this by setting(18)D0,τ=gak′/ξk′τk′∗−τk′+vτ.ℬ then chooses a random element t∈ℤp and sets D0,τ=gt. For all τ, it computes(19)D1,τ=gα′+α0t+vτξ0gaq−k′+1vτξk′τk′−τk′∗⋅gak′ξ0/ξk′τk′∗−τk′⋅∏j=1kτ−k′+1gaq−j+1ξj+k′τj∗+k′/ξk′τk′∗−τk′⋅∏j=k′+1kτ+1gaq−j+1ξjτj∗vτ=gα′gα0tgvτξ0+ξk′aq−k′+1τk′−τk′∗⋅gξ0ak′/ξk′τk′∗−τk′⋅∏j=k′+1kτ+1gξjaq−j+1+k′τj∗/ξk′τk′∗−τk′⋅∏j=k′+1kτ+1gξjaq−j+1τj∗vτ=gα′+aq+1gα0t⋅gξ0+ξk′aq−k′+1τk′−τk′∗ak′/ξk′τk′∗−τk′+vτ⋅∏j=k′+1kτ+1gξjaq−j+1τj∗ak′/ξk′τk′∗−τk′+vτ=gαgα0tgξ0+ξk′aq−k′+1τk′−τk′∗vτ˜⋅∏j=k′+1kτ+1gξjaq−j+1τj∗vτ˜=gαgα0tV0∏j=1k′Vjτjvτ˜∏j=k′+1kτ+1Vjτjvτ˜=gαgα0tV0∏j=1kτ+1Vjτjvτ˜=gαgα0tV0∏j=1kτVjτjvτ˜∵τkτ+1=0.Simulatorℬ also computes Kx and(20)Lj,τ=gξjaq+1+k′−j/ξk′τk′∗−τk′+vτξjaq−j+1=gξjaq−j+1ak′/ξk′τk′∗−τk′+vτ=Vjvτ˜.(iii)
Challenge: adversary A submits two equal length messages ℳ0 and ℳ1 with the matrix M∗ of dimension at most n columns to ℬ. ℬ flips a random coin b and encrypts ℳb under the access structure A∗, the revocation list ℛ∗, and the time Tc∗ with z-ary representation τ∗. It chooses random values μ1,μ2,…,μr such that μ=μ1+μ2+⋯+μr and creates the ciphertext components(21)C0=ℳbT⋅egs,gα′μ,C0′=gsμ.ForC0″, observe that since the challenge time is τ1∗,…,τk∗∗, the gai terms in Vi are cancelled out. Then, it sets C0″=gsξ0. ℬ also chooses random value y2′,y3′,…,yn∗′∈ℤp and shares the secret s using the vector x=s,y2′,y3′,…,yn∗′∈ℤpn. Next, it calculates(22)λk=x⋅εi,0e+εi,1M1∗+⋯+εi,mMm∗=x⋅εi,0e+Mk∗.And it generates the ciphertext componentCi.j as(23)Ci.j=gasvrMk,1+εk,0⋅∏i=2ngMk,iyi′.(i)
Fork=1,2,…,n, it defines Xk as the set of the index i such that ρi=ρk. Finally, ℬ builds the ciphertext component Ci,j∗ as(24)Ci,j∗=ga2∑m=1rIDcmgzxg−a2∑l=1rIDcl⋅∏i∈XkgMi⋅μ/biλkvγ=gzxλkvγ∏i∈XkgMi,1a2+Mi,2a3+⋯+Mi,nan+1λkvγ/bi.(ii)
Phase2: this phase is completely the same as the Phase 1.(iii)
Guess: the adversary A will finally output a guess b′ of b. ℬ outputs 0 to guess T=eg,gaq+1s if b′=b; otherwise, it outputs 1. When T is a tuple, ℬ gives a perfect simulation, so we have that the advantage of the simulator ℬ is the same as the advantage of the adversary A. Therefore, we have(25)Prℬy,T=eg,gaq+1s=0=12+AdvA.
The messageℳb is completely hidden from the adversary when T is a random group element, so we have Prℬy,T=R=0=1/2. Therefore, if A could attack scheme with nonnegligible advantage, then ℬ can also play the modified decisional q-parallel-BDHE game with nonnegligible advantage.


## 6. Performance Analysis

In this section, we first give a functional comparsion between our scheme and other schemes [23, 29] in Table 1.Table 1
Comparison of features.
SchemeInstant revokeShort revocation listKey updateCiphertext update[23]✓×××[29]✓✓✓×Ours✓✓✓✓Our scheme can implement user direct revocation, maintain a short revocation list, and update ciphertext. Compared with [23], our scheme can maintain a short revocation list and update ciphertext. Compared with [29], our scheme can update ciphertext. The ciphertext update can provide the encrypted data confidentiality by disqualifying the revoked users’ access to the encrypted data, especially that generated previously. We can periodically run a ciphertext update algorithm and do not need to execute a key update algorithm frequently because users have a reasonable validity time.Next, we mainly analyze the efficiency of the proposed scheme compared with [23, 29] in Table 2.Table 2
Efficiency comparison.
SchemePK sizeSK sizeCiphertext sizeDecryption time (of pairing)[23]U+3G1+G1S+2G12lR+1G1+G22IR+1[29]U+R+T+3G1+G2S+Z+R+1G1l+3G1+G22I+4OurU+T+3G1+G2S+Z+1G12lR′+1G1+G22IR′+2U: the max number of attributes in the system, G1: number of G1 elements, G2: number of G2 elements, S: the set of attributes created for a specific user, l: the number of attributes involved in the encryption process, I: the identity set defined in the system, R: the max number of the revoked users, R′: the length of the revocation list, T: the depth of the time tree, Z: best case Z=2, and worst case Z=TT+2/2.As shown in Table2, the efficiency of the proposed scheme is a little lower than scheme [23], but we can reduce the size of ciphertext by maintaining a short revocation list. In addition, the efficiency of our scheme is lower than scheme [29] in terms of the ciphertext size and the decryption time of pairing, but our scheme is more efficient in the size of PK and SK. The number of exponentiation operations in the KenGen algorithm in the scheme [29] is R times more than our scheme, and the number of exponentiation operations in the Encrypt algorithm in the scheme [29] is r times more than our scheme. Our scheme is practical that it can revoke users immediately, maintain a short revocation list, and update ciphertext, but loses the advantage of efficiency in the ciphertext size and the decryption time.


## 7. Conclusion

In this work, we propose a user R-CP-ABE scheme with ciphertext update. The scheme can implement user direct revocation, maintain a short revocation list, and update ciphertext by incorporating the identity-based and time-based revocable technique. We provide a ciphertext update mechanism, using only publicly available information, to disqualify the revoked users from accessing previously encrypted data. Our scheme supports the key update function for the nonrevoked users when their validity time expires. Once the validity time expires, the user’s key becomes invalid and cannot decrypt any newly generated ciphertext after the expiry date. The security is based on the modified decisionalq-parallel bilinear Diffie–Hellman Exponent problem. In the security model, we consider a strong adversary that can query the secret key of a user whose attribute set satisfies the challenge ciphertext access policy and whose identity is in the revocation list. In the future research, we will consider a more efficient mechanism for the user revocation and ciphertext update.



---

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