# Revocable Key-Aggregate Cryptosystem for Data Sharing in Cloud

Authors: Qingqing Gan; Xiaoming Wang; Daini Wu
Journal: Security and Communication Networks
 (2017)

---

## Abstract

With the rapid development of network and storage technology, cloud storage has become a new service mode, while data sharing and user revocation are important functions in the cloud storage. Therefore, according to the characteristics of cloud storage, a revocable key-aggregate encryption scheme is put forward based on subset-cover framework. The proposed scheme not only has the key-aggregate characteristics, which greatly simplifies the user’s key management, but also can revoke user access permissions, realizing the flexible and effective access control. When user revocation occurs, it allows cloud server to update the ciphertext so that revoked users can not have access to the new ciphertext, while nonrevoked users do not need to update their private keys. In addition, a verification mechanism is provided in the proposed scheme, which can verify the updated ciphertext and ensure that the user revocation is performed correctly. Compared with the existing schemes, this scheme can not only reduce the cost of key management and storage, but also realize user revocation and achieve user’s access control efficiently. Finally, the proposed scheme can be proved to be selective chosen-plaintext security in the standard model.


---

## Body

## 1. Introduction

With the continuous development of cloud computing technology, a new kind of data storage model called cloud storage has attracted great attention. Derived from cloud computing, cloud storage can provide online storage space through the network [1]. With the advantage of low cost, easy utilizing, and high scalability, it can meet the needs of the mass data storage and provide data sharing service, which has become the important area in the data storage technology. After requesting the storage service from cloud service providers, enterprises or individuals store a large amount of data to the cloud server, greatly reducing the burden of the local hardware infrastructure and saving the local storage overhead. What is more, its function of data sharing is regarded as very important for multiuser cloud computing environment. When data owners outsource their data in the server and want to share these data with other users, they can adopt techniques to delegate permission to these users. By this way, the legitimate users can have access to corresponding data from the cloud server so as to achieve the process of data sharing.However, when cloud storage brings great convenience for users dealing with large-scale data, it also brings new security issues and challenges [2]. Because the cloud server is not completely trusted, enterprises or individuals will lose absolute control over the data outsourced to the cloud data, which brings the worries about data security and privacy protection. So for these data, such as how to use encryption scheme to ensure the cloud security and how to protect the data privacy, realize effective data sharing, and reduce the user key management cost as much as possible, key-aggregate cryptosystem is brought forward at this moment. In such cryptosystem, user’s private keys can be aggregated together to be a single key and only using the single key can user decrypt the corresponding multiple encrypted files, which simplifies the user’s key management. It also grants different decryption access for different users and can be applied to the data sharing in cloud flexibly. Meanwhile, since user’s access changed dynamically and frequently in the cloud environment, how to realize user’s access control and revocation become vital problems to be solved. For example, when an employee leaves his company, he will no longer have permission to the company’s internal data. So, in order to meet the dynamic change of user access, it is necessary to consider the problem of user revocation.Therefore, according to the characteristics of cloud storage, the research and establishment of an efficient and secure revocable key-aggregate encryption scheme is very necessary and urgent, which has important theoretical significance and application value.


### 1.1. Contribution

In order to solve the key management problems and realize dynamic access control during data sharing more effectively, this paper has been focused on the study of revocable key-aggregate cryptosystem in cloud. Its main contribution shows the following:(1)
According to the characteristics of the key-aggregate cryptosystem and the needs for user revocation, this paper first makes formal definition about the revocable key-aggregate cryptosystem.(2)
Combining the subset-cover framework, this paper puts forward an efficient revocable key-aggregate encryption scheme based on multilinear maps, realizing the user’s access control and revocation. Our construction not only has the characteristics of key aggregation, which simplifies the user’s key management effectively, but also can delegate different users with different decryption permission and achieve revocation of user access rights, realizing the flexible access control effectively.(3)
Compared with the existing schemes, this paper analyzes the related performance for the proposed scheme. It indicates that our scheme not only keeps the users’ secret key and the ciphertext in constant-size, but also reduces the length of system parameters toOlog⁡N, where N is the maximum number of files in the system, thus saving the cost of storage and transmission efficiently. By updating ciphertext via the cloud servers, the proposed scheme realizes the user permissions revocation while legitimate users do not need to update their private keys. What is more, it provides a verification mechanism to ensure user revocation executed correctly.(4)
Lastly, security analysis shows that the proposed scheme is proved to be selective chosen-plaintext security based on Generalized DHDHE assumption in the standard model. In addition, we discuss a solution to extend our basic scheme to solve the rapid growing number of files in the cloud environment.


### 1.2. Related Works

In recent years, it has become a crucial problem to realize secure and effective data sharing, as well as reducing the key management costs in the cloud environment. How to reduce the number of keys that users have to save, thus simplifying the key management problems effectively, has been a hot research topic. In existing research results, they can mainly be divided into four kinds in reducing the cost of the key management: hierarchical key management scheme, key compression scheme based on symmetric encryption, identity-based key compression scheme, and other related solutions.In cloud storage, the hierarchical key management scheme generally utilizes tree structure, where the key of each nonleaf node can generate keys of its child nodes. And users only need to save the corresponding ancestor nodes, effectively simplifying the key management. This technology was first proposed by Akl and Taylor [7] and later has been applied to the cloud environment with the rise of cloud computing [8, 9]. For example, Ateniese et al. [10] put forward a predefined hierarchical key management scheme based on the logical key tree. However, the main drawback of hierarchical key management scheme was that only under certain conditions can it achieve effective key compression. This was because the node key can only access to the subtree of the node, if authorized files were from different branches, which in turn would increase the number of users’ private keys. So its key compression was limited; only when sharing all the documents from the same branch in the tree, it could achieve the effective compression of private key.In order to solve the issue that it needs to transport a large number of keys in the broadcast encryption scenario, Benaloh et al. [11] proposed a key compression scheme based on symmetric encryption. Its basic method is to split the entire ciphertext space into finite sets and generate a constant-size key corresponding to each of these sets, so as to realize the effect of key compression. Other schemes such as [12, 13] were also symmetrical encryption schemes trying to reduce the key size. Since these schemes were set in the environment of symmetric encryption, which required to share a symmetric key through secure channel, their application scenarios were greatly limited in the cloud environment.As Shamir [14] proposed the concept of identity-based encryption (IBE) and then Boneh and Franklin [15] put forward the first practical IBE scheme using bilinear pairings, it brought out the research of identity-based key compression scheme. Guo et al. [16] presented a multi-identity single key decryption scheme and proved its security in the random oracle model. In their scheme, when user adopted different identities as the public key in different scenarios, for example, user had more than one email address, it only needed to store a private key to decrypt multiple encrypted messages from different companies, remarkably cutting down the cost of the user key management. Then [17, 18] made improvements on the efficiency and achieved adaptive chosen-ciphertext security in the standard model. But in these schemes, key compression was restricted, which required all the keys from different identity divisions, and the length of ciphertext and public parameters were linearly related to the maximum number of keys that can be aggregated, which increased the overhead of storage and transmission. Sahai and Waters [19] proposed a fuzzy identity-based encryption (FIBE) scheme to take users’ biometric information as their identities, so that user’s identity was no longer a single one but was made up of several attributes. It allowed a private key to decrypt multiple ciphertexts and was proved to be secure in the standard model. However, this scheme required the ciphertext to be encrypted by identity that met certain conditions, so it could not achieve the flexible key compression.Other relevant solutions include the attribute-based encryption (ABE) and proxy reencryption (PRE). Waters [20] presented an ABE scheme that its private key was associated with the strategy, and ciphertext was associated with attributes and could decrypt when strategy matched with attributes. In their scheme, however, the length of private key was linearly related to the leaf nodes in the strategy access tree. Li et al. [21] applied ABE to share keys in group users, but the main concern was to resist collusion attacks, rather than key compression. Canetti and Hohenberger [22] put forward PRE scheme using the thought of transformation to turn the original ciphertext into the ciphertext encrypted by the user’s public key. However, such technology is essentially aimed at transferring the secure key storage to the cloud proxy server. In addition, a key management scheme based on secret sharing was proposed in [23], but it was suitable for wireless sensor networks.Recently, Chu et al. [24] first put forward the concept of key-aggregate cryptosystem (KAC) and constructed the first key-aggregate encryption scheme applied to data sharing in the cloud environment flexibly. The scheme was set in public key cryptosystem and it could aggregate users’ private key to be a single one, so that users only stored this aggregated key to decrypt multiple files. Most importantly, its aggregation could be achieved without conditions and kept the length of ciphertext in constant-size. However, the length of system parameters in their scheme was linearly related to the maximum number of files, and it did not provide a specific security proof. Soon afterwards, the thought of key-aggregate cryptosystem was adopted in [25–28], such as Dang et al. [27] who applied the key-aggregate cryptosystem in the wireless sensor network and proposed a fine-grained sharing scheme to the encrypted senor data. Sikhar et al. [3] proposed a dynamic key-aggregate encryption scheme to realize the user revocation. But one of its imitations was that once user revocation occurred, all legitimate users needed to update their private keys, which brought expensive overhead of key update.


### 1.3. Organization

The rest of the paper is organized as follows: Section2 introduces some related knowledge, including multilinear maps, complexity assumption, and subset-cover framework. In Section 3 we discuss the definition, the security model, and system model of the revocable key-aggregate cryptosystem. Section 4 details our new construction and Section 5 shows the evaluation of our proposed scheme, containing performance analysis and the security analysis. Then in Section 6, we have some discussions and present an extension for our basic scheme. Finally, we conclude this paper and look forward to the future work in Section 7.


## 1.1. Contribution

In order to solve the key management problems and realize dynamic access control during data sharing more effectively, this paper has been focused on the study of revocable key-aggregate cryptosystem in cloud. Its main contribution shows the following:(1)
According to the characteristics of the key-aggregate cryptosystem and the needs for user revocation, this paper first makes formal definition about the revocable key-aggregate cryptosystem.(2)
Combining the subset-cover framework, this paper puts forward an efficient revocable key-aggregate encryption scheme based on multilinear maps, realizing the user’s access control and revocation. Our construction not only has the characteristics of key aggregation, which simplifies the user’s key management effectively, but also can delegate different users with different decryption permission and achieve revocation of user access rights, realizing the flexible access control effectively.(3)
Compared with the existing schemes, this paper analyzes the related performance for the proposed scheme. It indicates that our scheme not only keeps the users’ secret key and the ciphertext in constant-size, but also reduces the length of system parameters toOlog⁡N, where N is the maximum number of files in the system, thus saving the cost of storage and transmission efficiently. By updating ciphertext via the cloud servers, the proposed scheme realizes the user permissions revocation while legitimate users do not need to update their private keys. What is more, it provides a verification mechanism to ensure user revocation executed correctly.(4)
Lastly, security analysis shows that the proposed scheme is proved to be selective chosen-plaintext security based on Generalized DHDHE assumption in the standard model. In addition, we discuss a solution to extend our basic scheme to solve the rapid growing number of files in the cloud environment.


## 1.2. Related Works

In recent years, it has become a crucial problem to realize secure and effective data sharing, as well as reducing the key management costs in the cloud environment. How to reduce the number of keys that users have to save, thus simplifying the key management problems effectively, has been a hot research topic. In existing research results, they can mainly be divided into four kinds in reducing the cost of the key management: hierarchical key management scheme, key compression scheme based on symmetric encryption, identity-based key compression scheme, and other related solutions.In cloud storage, the hierarchical key management scheme generally utilizes tree structure, where the key of each nonleaf node can generate keys of its child nodes. And users only need to save the corresponding ancestor nodes, effectively simplifying the key management. This technology was first proposed by Akl and Taylor [7] and later has been applied to the cloud environment with the rise of cloud computing [8, 9]. For example, Ateniese et al. [10] put forward a predefined hierarchical key management scheme based on the logical key tree. However, the main drawback of hierarchical key management scheme was that only under certain conditions can it achieve effective key compression. This was because the node key can only access to the subtree of the node, if authorized files were from different branches, which in turn would increase the number of users’ private keys. So its key compression was limited; only when sharing all the documents from the same branch in the tree, it could achieve the effective compression of private key.In order to solve the issue that it needs to transport a large number of keys in the broadcast encryption scenario, Benaloh et al. [11] proposed a key compression scheme based on symmetric encryption. Its basic method is to split the entire ciphertext space into finite sets and generate a constant-size key corresponding to each of these sets, so as to realize the effect of key compression. Other schemes such as [12, 13] were also symmetrical encryption schemes trying to reduce the key size. Since these schemes were set in the environment of symmetric encryption, which required to share a symmetric key through secure channel, their application scenarios were greatly limited in the cloud environment.As Shamir [14] proposed the concept of identity-based encryption (IBE) and then Boneh and Franklin [15] put forward the first practical IBE scheme using bilinear pairings, it brought out the research of identity-based key compression scheme. Guo et al. [16] presented a multi-identity single key decryption scheme and proved its security in the random oracle model. In their scheme, when user adopted different identities as the public key in different scenarios, for example, user had more than one email address, it only needed to store a private key to decrypt multiple encrypted messages from different companies, remarkably cutting down the cost of the user key management. Then [17, 18] made improvements on the efficiency and achieved adaptive chosen-ciphertext security in the standard model. But in these schemes, key compression was restricted, which required all the keys from different identity divisions, and the length of ciphertext and public parameters were linearly related to the maximum number of keys that can be aggregated, which increased the overhead of storage and transmission. Sahai and Waters [19] proposed a fuzzy identity-based encryption (FIBE) scheme to take users’ biometric information as their identities, so that user’s identity was no longer a single one but was made up of several attributes. It allowed a private key to decrypt multiple ciphertexts and was proved to be secure in the standard model. However, this scheme required the ciphertext to be encrypted by identity that met certain conditions, so it could not achieve the flexible key compression.Other relevant solutions include the attribute-based encryption (ABE) and proxy reencryption (PRE). Waters [20] presented an ABE scheme that its private key was associated with the strategy, and ciphertext was associated with attributes and could decrypt when strategy matched with attributes. In their scheme, however, the length of private key was linearly related to the leaf nodes in the strategy access tree. Li et al. [21] applied ABE to share keys in group users, but the main concern was to resist collusion attacks, rather than key compression. Canetti and Hohenberger [22] put forward PRE scheme using the thought of transformation to turn the original ciphertext into the ciphertext encrypted by the user’s public key. However, such technology is essentially aimed at transferring the secure key storage to the cloud proxy server. In addition, a key management scheme based on secret sharing was proposed in [23], but it was suitable for wireless sensor networks.Recently, Chu et al. [24] first put forward the concept of key-aggregate cryptosystem (KAC) and constructed the first key-aggregate encryption scheme applied to data sharing in the cloud environment flexibly. The scheme was set in public key cryptosystem and it could aggregate users’ private key to be a single one, so that users only stored this aggregated key to decrypt multiple files. Most importantly, its aggregation could be achieved without conditions and kept the length of ciphertext in constant-size. However, the length of system parameters in their scheme was linearly related to the maximum number of files, and it did not provide a specific security proof. Soon afterwards, the thought of key-aggregate cryptosystem was adopted in [25–28], such as Dang et al. [27] who applied the key-aggregate cryptosystem in the wireless sensor network and proposed a fine-grained sharing scheme to the encrypted senor data. Sikhar et al. [3] proposed a dynamic key-aggregate encryption scheme to realize the user revocation. But one of its imitations was that once user revocation occurred, all legitimate users needed to update their private keys, which brought expensive overhead of key update.


## 1.3. Organization

The rest of the paper is organized as follows: Section2 introduces some related knowledge, including multilinear maps, complexity assumption, and subset-cover framework. In Section 3 we discuss the definition, the security model, and system model of the revocable key-aggregate cryptosystem. Section 4 details our new construction and Section 5 shows the evaluation of our proposed scheme, containing performance analysis and the security analysis. Then in Section 6, we have some discussions and present an extension for our basic scheme. Finally, we conclude this paper and look forward to the future work in Section 7.


## 2. Preliminaries

In this section we describe some basic primitives and concepts that are used in our scheme.


### 2.1. Multilinear Maps

Multilinear maps were first put forward by Boneh and Silverberg [29], making the research and application of multilinear maps be more and more widely. Multilinear maps mainly consist of the following two algorithms:(1)
Setupn: the Setup algorithm outputs an n-linear map, which contains n groups G=G1,G2,…,Gn with prime order p and generators gi∈Gi.(2)
ei,jg,h: the map algorithm takes two elements g∈Gi and h∈Gj as input, while i+j≤n, and outputs an element in Gi+j satisfying ei,jgia,gjb=gi+jab. We often leave out the subscripts to be written as e. The generalization of e with multiple inputs can be donated as eh1,h2,…,hk=eh1,eh2,…,hk.In the asymmetric multilinear maps [30], group is divided by a vector and the map operations make Gv1×Gv2into Gv1+v2. The definition shows the following:(1)
Setupn: the Setup algorithm takes a positive integer vector n∈Zλ as input and outputs an n-linear map, which contains a set of groups Gv with prime order p, and generators gv∈Gv, whilev are nonnegative integer vectors meeting v≤n. Assume ei be the vector with 1 at the position i and 0 at else positions. Then Gei are the source groups, Gn is defined as the target group, and the rest of the groups are intermediate group.(2)
ev1,v2g,h: the map algorithm inputs two elements g∈Gv1 and h∈Gv2 with v1+v2≤n and outputs an element of Gv1+v2 such that ev1,v2gv1a,gv2b=gv1+v2ab. Similarly, we leave out the subscripts to be written as e and also generalize e with multiple inputs as eh1,h2,…,hk=eh1,eh2,…,hk.


### 2.2. Complexity Assumption

We introduce a new complexity assumption named Generalized DHDHE. This new assumption is the variant version of the well-known Decisionaln-Hybrid Diffie-Hellman Exponent (DHDHE) proposed by Boneh et al. [30].Assumption 1 (Generalized Decisionaln-Hybrid Diffie-Hellman Exponent, Generalized DHDHE).
Letparams′←Setup′(2n). Choose random α∈Zp; set Xl=gelα(2l) for l=0,1,…,n-1; and set Xn=genα(2n+1) for l=n. Randomly select t1∈Zp, t2∈Zp, while t=t1+t2, and let Y1=gnt1,  Y2=gnt2. Given {Xi}i∈{0,1,…,n},Y1,Y2,K, the goal is to distinguish K=g2ntα(2n) from a random element in G2n.For a polynomial-time adversaryA, its advantages to Generalized DHDHE problem are defined as(1)AdvAWeak DHDHE=PrAXii∈0,1,…,n,Y1,Y2,K=g2ntα2n=1-PrAXii∈0,1,…,n,Y1,Y2,K=g2nr=1.From here we can see that this new assumption is the generalization of DHDHE assumption. Specifically, if we multiplyY1 and Y2, Generalized DHDHE assumption can be reduced to DHDHE assumption in [30].Definition 2.
We say the Generalized DHDHE assumption holds if, for any polynomial-time adversaryA, A has a negligible advantage in solving the Generalized DHDHE problem.


### 2.3. Subset-Cover Framework

Naor et al. [4] first proposed the subset-cover framework and applied it to the broadcast encryption scheme, realizing the dynamic authorization of the user. The subset-cover framework includes complete subtree (CS) method and subset difference (SD) method. This paper mainly introduces CS method, shown as follows.LetT be a full binary tree with depth d. Thus the number of leaf nodes in the tree is 2d-1, representing 2d-1 users. First, for each user u, we define a path set denoted by path(u), containing all the nodes passing through the root node to leaf node. When given a user revocation set R, let Si1,Si2,…,Sim be the complete subtrees in T rooted at the nodes of outdegree one in Steiner Tree ST(R), and Si1,Si2,…,Sim are not in the ST(R). We said that Si1,Si2,…,Sim cover all the nonrevoked nodes in T, denoted by cover(R). Take the example in Figure 1. Given the full binary tree T with eight leaf nodes, we get the user sets U=x8,x9,…,x15. Then the path set for each user can be obtained as path(x8)=x1,x2,x4,x8, path(x12)=x1,x3,x6,x12, and so on. Suppose the user revocation set R=x8,x10; then ST(R) is shown in the dotted box in Figure 1, so that cover(R)=x3,x9,x11 including all the nonrevoked users.Figure 1
Subset-cover framework: Complete Subtree method.When constructing the scheme based on the subset-cover framework, the path set is embedded in private key, while the cover set is related to the ciphertext. If and only ifpath(u)∩coverR≠ϕ, the user u can take the next step to the decryption. In the CS method as shown in Figure 1, only legitimate users, such as x9,x12, meet the conditions. For revoked user u, since pathu∩coverR=ϕ, then he is unable to complete the decryption, as x8 in Figure 1.


## 2.1. Multilinear Maps

Multilinear maps were first put forward by Boneh and Silverberg [29], making the research and application of multilinear maps be more and more widely. Multilinear maps mainly consist of the following two algorithms:(1)
Setupn: the Setup algorithm outputs an n-linear map, which contains n groups G=G1,G2,…,Gn with prime order p and generators gi∈Gi.(2)
ei,jg,h: the map algorithm takes two elements g∈Gi and h∈Gj as input, while i+j≤n, and outputs an element in Gi+j satisfying ei,jgia,gjb=gi+jab. We often leave out the subscripts to be written as e. The generalization of e with multiple inputs can be donated as eh1,h2,…,hk=eh1,eh2,…,hk.In the asymmetric multilinear maps [30], group is divided by a vector and the map operations make Gv1×Gv2into Gv1+v2. The definition shows the following:(1)
Setupn: the Setup algorithm takes a positive integer vector n∈Zλ as input and outputs an n-linear map, which contains a set of groups Gv with prime order p, and generators gv∈Gv, whilev are nonnegative integer vectors meeting v≤n. Assume ei be the vector with 1 at the position i and 0 at else positions. Then Gei are the source groups, Gn is defined as the target group, and the rest of the groups are intermediate group.(2)
ev1,v2g,h: the map algorithm inputs two elements g∈Gv1 and h∈Gv2 with v1+v2≤n and outputs an element of Gv1+v2 such that ev1,v2gv1a,gv2b=gv1+v2ab. Similarly, we leave out the subscripts to be written as e and also generalize e with multiple inputs as eh1,h2,…,hk=eh1,eh2,…,hk.


## 2.2. Complexity Assumption

We introduce a new complexity assumption named Generalized DHDHE. This new assumption is the variant version of the well-known Decisionaln-Hybrid Diffie-Hellman Exponent (DHDHE) proposed by Boneh et al. [30].Assumption 1 (Generalized Decisionaln-Hybrid Diffie-Hellman Exponent, Generalized DHDHE).
Letparams′←Setup′(2n). Choose random α∈Zp; set Xl=gelα(2l) for l=0,1,…,n-1; and set Xn=genα(2n+1) for l=n. Randomly select t1∈Zp, t2∈Zp, while t=t1+t2, and let Y1=gnt1,  Y2=gnt2. Given {Xi}i∈{0,1,…,n},Y1,Y2,K, the goal is to distinguish K=g2ntα(2n) from a random element in G2n.For a polynomial-time adversaryA, its advantages to Generalized DHDHE problem are defined as(1)AdvAWeak DHDHE=PrAXii∈0,1,…,n,Y1,Y2,K=g2ntα2n=1-PrAXii∈0,1,…,n,Y1,Y2,K=g2nr=1.From here we can see that this new assumption is the generalization of DHDHE assumption. Specifically, if we multiplyY1 and Y2, Generalized DHDHE assumption can be reduced to DHDHE assumption in [30].Definition 2.
We say the Generalized DHDHE assumption holds if, for any polynomial-time adversaryA, A has a negligible advantage in solving the Generalized DHDHE problem.


## 2.3. Subset-Cover Framework

Naor et al. [4] first proposed the subset-cover framework and applied it to the broadcast encryption scheme, realizing the dynamic authorization of the user. The subset-cover framework includes complete subtree (CS) method and subset difference (SD) method. This paper mainly introduces CS method, shown as follows.LetT be a full binary tree with depth d. Thus the number of leaf nodes in the tree is 2d-1, representing 2d-1 users. First, for each user u, we define a path set denoted by path(u), containing all the nodes passing through the root node to leaf node. When given a user revocation set R, let Si1,Si2,…,Sim be the complete subtrees in T rooted at the nodes of outdegree one in Steiner Tree ST(R), and Si1,Si2,…,Sim are not in the ST(R). We said that Si1,Si2,…,Sim cover all the nonrevoked nodes in T, denoted by cover(R). Take the example in Figure 1. Given the full binary tree T with eight leaf nodes, we get the user sets U=x8,x9,…,x15. Then the path set for each user can be obtained as path(x8)=x1,x2,x4,x8, path(x12)=x1,x3,x6,x12, and so on. Suppose the user revocation set R=x8,x10; then ST(R) is shown in the dotted box in Figure 1, so that cover(R)=x3,x9,x11 including all the nonrevoked users.Figure 1
Subset-cover framework: Complete Subtree method.When constructing the scheme based on the subset-cover framework, the path set is embedded in private key, while the cover set is related to the ciphertext. If and only ifpath(u)∩coverR≠ϕ, the user u can take the next step to the decryption. In the CS method as shown in Figure 1, only legitimate users, such as x9,x12, meet the conditions. For revoked user u, since pathu∩coverR=ϕ, then he is unable to complete the decryption, as x8 in Figure 1.


## 3. Revocable Key-Aggregate Cryptosystem

Since the delegated users in cloud have the feature of dynamic change, revocable key-aggregate cryptosystem is essential for consummating the user revocation function in KAC.


### 3.1. Definition

Revocable key-aggregate cryptosystem (RKAC) is an extension of KAC such that a user can be revoked if his credential is expired. A revocable key-aggregate encryption scheme consists of seven polynomial-time algorithms as Setup, KeyGen, Encrypt, Extract, Update, Decrypt, and Verify, which are defined as follows:(1)
Setup1λ,n: the Setup algorithm takes as input a security parameter 1λ and the maximum number of files n. It outputs public parameters params.(2)
KeyGenparams: the key generation algorithm takes as input public parameters params. It generates a public key PK and a master secret key msk.(3)
EncryptPK,i,m,params: the encryption algorithm takes as input public key PK, an index i denoting the file, a message m, and public parameters params. It outputs a ciphertext C.(4)
Extractmsk,uid,S,params: the Extract algorithm takes as input the master secret key msk and a setS of indices corresponding to different files, user identity uid, and public parameters params. It outputs users’ private key SK.(5)
UpdatePK,R,C,params: the update algorithm takes as input the public key PK, the user revocation set R, a ciphertext C, and public parameters params. It outputs an updated ciphertext C′.(6)
DecryptC,SK,S,i,R,params: the decryption algorithm takes as input a ciphertext C, user private key SK, the set S, an index i denoting the ciphertext C, the user revocation set R, and public parameters params. If i∈S∧uid∉R, it outputs the result m or else outputs ⊥.(7)
VerifyC,C′,PK,params: the Verify algorithm takes as input a ciphertext C, an updated ciphertext C′, public key PK, and public parameters params. If the cloud server has executed the revocation honestly and updated the ciphertext correctly, it outputs 1 or else outputs 0.


### 3.2. Security Model

For RKAC, we present its security model through the game between a challengerChal and a polynomial-time adversary A. The selective security property of RKAC under indistinguishable chosen-ciphertext attack (IND-CCA) is defined as follows.Init.
A initially submits a challenge file index i∗ and a revoked identity set R∗.Setup.
C
h
a
l generates public parameters params and (PK, msk) by running Setup1λ,n and KeyGenparams. It keeps msk secretly to itself and gives params and PK to A.Phase 1.
A adaptively requests a series of queries. These queries are processed as follows:(i)
Step1 (extraction query): for any file index set S(i∗∉S) and identity uid(uid∈R∗), Chal invokes the Extract algorithm Extractmsk,uid,S,params and sends the generated private key SK=KS,Kuid to A.(ii)
Step2 (decryption query): for any ciphertext Ci, file index set S(i∗∉S), and identity uid(uid∈R∗), the challenger Chal executes the decryption algorithm DecryptCi,SK,S,i,R,params and sends the obtained plaintext to A.Challenge. Once the adversary A decides to end Phase 1, it submits two challenge messages m0,m1∈M with equal length. Chal flips a random coin b∈0,1 and sets C=EncryptPK,i∗,mb,params, C∗=UpdateC,R∗ and then gives the challenge ciphertext C∗ to A.Phase 2.
A continues to request a series of adaptive queries, but with the restrictions that it cannot perform the decryption query to C∗. The challenger Chal adopts the same method as in Phase 1 to answer the queries.Guess. Finally, A outputs a guess b′∈0,1 and wins the game if b′=b.The acquired advantage of the adversaryA for the RKAC scheme is defined as AdvARKAC=Prb′=b-1/2.Definition 3.
If, for any polynomial-timet and adversary A through q queries in the above game, its advantage for RKAC scheme AdvARKAC≤ε, one said this RKAC scheme is selective t,q,ε-IND-CCA security.Definition 4.
If, for any polynomial-timet and adversary A through q queries in the above game without the decryption query, its advantage for RKAC scheme AdvARKAC≤ε, one said this RKAC scheme is selective t,q,ε-IND-CPA security.


### 3.3. System Model

Applying the RKAC in a cloud environment, the model is shown in Figure2. It consists of three entities: cloud service provider (CSP), the data owner (DO), and user.Figure 2
The model for RKAC.When the data owner Alice wants to share multiple filesm1,m2,…,mnwith others through the cloud server utilizing revocable key-aggregate encryption scheme, Alice first runs Setup algorithm to get the system parameters params. Then Alice executes KeyGenparams to get a random public/master secret key-pair (PK,msk) and kept msk secretly. After that, Alice and anyone who cooperated with Alice can run the encryption algorithm EncryptPK,i,R,m,params and upload the encrypted files to the cloud server. Once Alice hopes to share several of these files to user Bob, Alice will run the algorithm Extractmsk,uid,S,params to generate a private key SK for Bob according to authorized files’ indices and the user’s identity. Since SK is a fixed size, it is easy for Alice to pass SK to Bob through safe channel with small communication cost. Whenever Alice wants to revoke users, Alice will send the user revocation list R to CSP. Then CSP calls the algorithm UpdatePK,R,C,params to update the corresponding ciphertext. If and only if Bob has not been revoked, Bob downloads the updated ciphertext from the cloud server and runs the algorithm DecryptC,SK,S,i,R,params with the use of the private key to obtain plaintext. And if the user has been revoked, such as David in Figure 2, he will not be able to decrypt the updated ciphertext, thus withdrawing David’s permission to the files. Finally, by invoking the algorithm VerifyC,C′,params, Alice can achieve the verification of the updated ciphertext, to ensure that the user revocation is effectively implemented.


## 3.1. Definition

Revocable key-aggregate cryptosystem (RKAC) is an extension of KAC such that a user can be revoked if his credential is expired. A revocable key-aggregate encryption scheme consists of seven polynomial-time algorithms as Setup, KeyGen, Encrypt, Extract, Update, Decrypt, and Verify, which are defined as follows:(1)
Setup1λ,n: the Setup algorithm takes as input a security parameter 1λ and the maximum number of files n. It outputs public parameters params.(2)
KeyGenparams: the key generation algorithm takes as input public parameters params. It generates a public key PK and a master secret key msk.(3)
EncryptPK,i,m,params: the encryption algorithm takes as input public key PK, an index i denoting the file, a message m, and public parameters params. It outputs a ciphertext C.(4)
Extractmsk,uid,S,params: the Extract algorithm takes as input the master secret key msk and a setS of indices corresponding to different files, user identity uid, and public parameters params. It outputs users’ private key SK.(5)
UpdatePK,R,C,params: the update algorithm takes as input the public key PK, the user revocation set R, a ciphertext C, and public parameters params. It outputs an updated ciphertext C′.(6)
DecryptC,SK,S,i,R,params: the decryption algorithm takes as input a ciphertext C, user private key SK, the set S, an index i denoting the ciphertext C, the user revocation set R, and public parameters params. If i∈S∧uid∉R, it outputs the result m or else outputs ⊥.(7)
VerifyC,C′,PK,params: the Verify algorithm takes as input a ciphertext C, an updated ciphertext C′, public key PK, and public parameters params. If the cloud server has executed the revocation honestly and updated the ciphertext correctly, it outputs 1 or else outputs 0.


## 3.2. Security Model

For RKAC, we present its security model through the game between a challengerChal and a polynomial-time adversary A. The selective security property of RKAC under indistinguishable chosen-ciphertext attack (IND-CCA) is defined as follows.Init.
A initially submits a challenge file index i∗ and a revoked identity set R∗.Setup.
C
h
a
l generates public parameters params and (PK, msk) by running Setup1λ,n and KeyGenparams. It keeps msk secretly to itself and gives params and PK to A.Phase 1.
A adaptively requests a series of queries. These queries are processed as follows:(i)
Step1 (extraction query): for any file index set S(i∗∉S) and identity uid(uid∈R∗), Chal invokes the Extract algorithm Extractmsk,uid,S,params and sends the generated private key SK=KS,Kuid to A.(ii)
Step2 (decryption query): for any ciphertext Ci, file index set S(i∗∉S), and identity uid(uid∈R∗), the challenger Chal executes the decryption algorithm DecryptCi,SK,S,i,R,params and sends the obtained plaintext to A.Challenge. Once the adversary A decides to end Phase 1, it submits two challenge messages m0,m1∈M with equal length. Chal flips a random coin b∈0,1 and sets C=EncryptPK,i∗,mb,params, C∗=UpdateC,R∗ and then gives the challenge ciphertext C∗ to A.Phase 2.
A continues to request a series of adaptive queries, but with the restrictions that it cannot perform the decryption query to C∗. The challenger Chal adopts the same method as in Phase 1 to answer the queries.Guess. Finally, A outputs a guess b′∈0,1 and wins the game if b′=b.The acquired advantage of the adversaryA for the RKAC scheme is defined as AdvARKAC=Prb′=b-1/2.Definition 3.
If, for any polynomial-timet and adversary A through q queries in the above game, its advantage for RKAC scheme AdvARKAC≤ε, one said this RKAC scheme is selective t,q,ε-IND-CCA security.Definition 4.
If, for any polynomial-timet and adversary A through q queries in the above game without the decryption query, its advantage for RKAC scheme AdvARKAC≤ε, one said this RKAC scheme is selective t,q,ε-IND-CPA security.


## 3.3. System Model

Applying the RKAC in a cloud environment, the model is shown in Figure2. It consists of three entities: cloud service provider (CSP), the data owner (DO), and user.Figure 2
The model for RKAC.When the data owner Alice wants to share multiple filesm1,m2,…,mnwith others through the cloud server utilizing revocable key-aggregate encryption scheme, Alice first runs Setup algorithm to get the system parameters params. Then Alice executes KeyGenparams to get a random public/master secret key-pair (PK,msk) and kept msk secretly. After that, Alice and anyone who cooperated with Alice can run the encryption algorithm EncryptPK,i,R,m,params and upload the encrypted files to the cloud server. Once Alice hopes to share several of these files to user Bob, Alice will run the algorithm Extractmsk,uid,S,params to generate a private key SK for Bob according to authorized files’ indices and the user’s identity. Since SK is a fixed size, it is easy for Alice to pass SK to Bob through safe channel with small communication cost. Whenever Alice wants to revoke users, Alice will send the user revocation list R to CSP. Then CSP calls the algorithm UpdatePK,R,C,params to update the corresponding ciphertext. If and only if Bob has not been revoked, Bob downloads the updated ciphertext from the cloud server and runs the algorithm DecryptC,SK,S,i,R,params with the use of the private key to obtain plaintext. And if the user has been revoked, such as David in Figure 2, he will not be able to decrypt the updated ciphertext, thus withdrawing David’s permission to the files. Finally, by invoking the algorithm VerifyC,C′,params, Alice can achieve the verification of the updated ciphertext, to ensure that the user revocation is effectively implemented.


## 4. Main Construction

Our main construction of the revocable key-aggregate encryption scheme is based on multilinear maps and realizes data sharing and user revocation in cloud storage securely and efficiently.


### 4.1. Basic Idea

In KAC, the aggregation of file indices is embedded in the user’s private key so that authorized users store the aggregate key to realize the access to multiple files. However, the access of user in system is changed dynamically, requiring KAC to support user revocation. Therefore, in order to construct a revocable key-aggregate encryption scheme, two mainly challenges are remained to be solved. One is how to construct an efficient scheme with key-aggregate function, the other is how to realize revoking users securely while not affecting the legitimate users’ access to files.For the first challenge, we are inspired by Boneh et al.’s broadcast encryption [30]. Based on this scheme, we try to construct a key-aggregate scheme to keep the users’ secret key and the ciphertext in constant-size. With the multilinear maps, it can reduces the length of system parameters to Olog⁡N, thus saving the cost of storage and transmission efficiently.For the second challenge, our inspiration comes from Shi et al. [6] revocable key-policy ABE scheme. The scheme not only realizes the direct user revocation, but also achieves the function of ciphertext delegation by a third-party server. What is more, it provides a verification mechanism to ensure the correctness of the ciphertext delegation, which has been of great significance. However, in their scheme, the user private key is related to the access structure and path set in subset-cover framework. Besides that, Shi et al. [6] scheme is only proved to be secure under the random oracle model. So we try to combine Naor et al. [4] subset-cover framework with our scheme for user revocation. In addition, we make improvement of the complete subtree method of subset-cover framework in [4] to aggregate the path set for each user as private key, so as to realize the user’s key aggregation and simplify the key management effectively.Therefore, this paper proposes a revocable key-aggregate encryption scheme and proves its security in the standard model. The main thought of the scheme lies in constructing the ciphertext and the private key. The ciphertext of the new scheme includes not only the file index, but also the user revocation set, realizing the user revocable directly. At the same time, the private key is correspondingly divided into two parts. One is the aggregation of the file index set, and the other is the aggregation of the path set for each user, so as to realize the user’s key aggregation effectively. Through the above method, only the legitimate users have access to the appropriate file, realizing the file access control function in the system effectively. This new scheme achieves the ciphertext updating through the cloud servers to save the computational overhead of data owner; when the user revocation occurs, nonrevoked user does not need to update his private key, greatly reducing the key update expensive cost and the burden of key delegate authority; because the cloud server is not completely trusted, we consider to provide a verification mechanism for the scheme, so that the data owner can validate the updated ciphertext to make sure the user revocation is carried out correctly.


### 4.2. Scheme Design

LetSetup′ be the Setup algorithm for a multilinear map, where outputs group with order p, respectively. Let T be a full binary tree with depth d(1≤d≤n), where the leaf stands for user. Number all the nodes in T from one to 2d-1; then our scheme consists of the following algorithms:(1)
Setup1λ,n: take as input the length n of index. Let {0,1}n∖{0n} be the index space. Therefore the maximum number of files in the system is N=2n-1. Let n be the all-ones vector with length n+1. Run Setup′2n to obtain the public parameters params′ for a multilinear map of target group G2n. Select a random α∈Zp, and set Xl=gelα(2l) for l=0,1,…,n-1, and set Xn=genα(2n+1)  for l=n. Lastly, let W=g2n2α(2n). It outputs the public parameters params=params′,{Xi}i∈{0,1,…,n},W.(2)
KeyGenparams: choose a random β∈Zp,  γ∈Zp and compute μ=gnβ,  v=gnγ, output PK=(μ,v),msk=(β,γ).(3)
EncryptPK,i,m,params: for a message m and an index i∈1,2,…,2n-1, randomly pick t1∈Zp and compute K=Wt1=g2nt1α(2n). The ciphertext is created as(2)C=c1,c2,c3=gnt1,vgnαit1,m·Wt1.(4)
Extractmsk,uid,S,params: given the user identity uid∈0,1d, make use of the CS method in the full binary tree T to get the user’s path path(uid)={yu0,…,yud}, such that yu0=root and yud=uid. Compute Puid=∏y∈path(uid)Z2n-y; then the path aggregate key Kuid=Puidβ. For the set S⊆1,2,…,2n-1, the index aggregate key is computed as KS=∏j∈SZ2n-jγ. Since S does not include 0, Z2n-j=gnα2n-j can always be retrieved from params. The user’s private key is set to SK=KS,Kuid.(5)
UpdatePK,R,C,params: for user revocation set R, compute coverR according to the CS method in subset-cover framework. For x∈coverR, compute Px=gnαx. Choose a random t2∈Zp; then get c3′=c3·Wt2=m·Wt1+t2. Suppose that t=t1+t2; then we have c3′=m·Wt. Compute c4=gnt2, c5=μPxt2x∈cover(R). Finally get the updated ciphertext as follows:(3)C′=c1,c2,c3′,c4,c5=gnt1,vgnαit1,m·Wt,gnt2,μPxt2x∈coverR.(6)
DecryptC,SK,S,i,R,params: when user receives the ciphertext C with the index i, if either the index i∉S or the user’s identity uid∈R, then return ⊥. Otherwise, for x=path(uid)∩coverR, decryption can be done as follows:(4)m=c3·eKS·∏j∈S,j≠iZ2n-j+i,c1e∏j∈SZ2n-j,c2·eKuid·∏y∈pathuid,y≠xZ2n-y+x,c4ePuid,c5.(7)
VerifyC,C′,PK,params: to verify whether the cloud server has executed the revocation correctly and honestly, the equation eμPx,c4=?ec5,gncan be used and it returns 0 or 1. For data owner, in order to verify whether the updated ciphertext c3′ is right or not, he can use the equation ec3′/c3,gn=?eW,c4. If returning 1, it means right or else means wrong.For correctness, we can see that (5)c3·eKS·∏j∈S,j≠iZ2n-j+i,c1e∏j∈SZ2n-j,c2·eKuid·∏y∈pathuid,y≠xZ2n-y+x,c4ePuid,c5=c3·e∏j∈SZ2n-jγ·∏j∈S,j≠iZ2n-j+i,gnt1e∏j∈SZ2n-j,vgnαit1·ePuidβ·∏y∈pathuid,y≠xZ2n-y+x,gnt2ePuid,μgnαxt2=c3·e∏j∈SZ2n-jγ,gnt1e∏j∈SZ2n-j,vt1·e∏j∈S,j≠iZ2n-j+i,gnt1e∏j∈SZ2n-j,gnαit1·ePuidβ,gnt2ePuid,μt2·e∏y∈pathuid,y≠xZ2n-y+x,gnt2e∏y∈pathuidZ2n-j,gnαxt2=c3·e∏j∈S,j≠iZ2n-j+i,gnt1e∏j∈SZ2n-j,gnαit1·e∏y∈pathuid,y≠xZ2n-y+x,gnt2e∏y∈pathuidZ2n-j,gnαxt2=m·Wt·egn∑j∈S,j≠iα2n-j+i,gnt1egn∑j∈Sα2n-j,gnαit1·egn∑y∈pathuid,y≠xα2n-y+x,gnt2egn∑y∈pathuidα2n-y,gnαxt2=m·Wtg2nα2nt1+t2=m·Wtg2nα2nt=m.


## 4.1. Basic Idea

In KAC, the aggregation of file indices is embedded in the user’s private key so that authorized users store the aggregate key to realize the access to multiple files. However, the access of user in system is changed dynamically, requiring KAC to support user revocation. Therefore, in order to construct a revocable key-aggregate encryption scheme, two mainly challenges are remained to be solved. One is how to construct an efficient scheme with key-aggregate function, the other is how to realize revoking users securely while not affecting the legitimate users’ access to files.For the first challenge, we are inspired by Boneh et al.’s broadcast encryption [30]. Based on this scheme, we try to construct a key-aggregate scheme to keep the users’ secret key and the ciphertext in constant-size. With the multilinear maps, it can reduces the length of system parameters to Olog⁡N, thus saving the cost of storage and transmission efficiently.For the second challenge, our inspiration comes from Shi et al. [6] revocable key-policy ABE scheme. The scheme not only realizes the direct user revocation, but also achieves the function of ciphertext delegation by a third-party server. What is more, it provides a verification mechanism to ensure the correctness of the ciphertext delegation, which has been of great significance. However, in their scheme, the user private key is related to the access structure and path set in subset-cover framework. Besides that, Shi et al. [6] scheme is only proved to be secure under the random oracle model. So we try to combine Naor et al. [4] subset-cover framework with our scheme for user revocation. In addition, we make improvement of the complete subtree method of subset-cover framework in [4] to aggregate the path set for each user as private key, so as to realize the user’s key aggregation and simplify the key management effectively.Therefore, this paper proposes a revocable key-aggregate encryption scheme and proves its security in the standard model. The main thought of the scheme lies in constructing the ciphertext and the private key. The ciphertext of the new scheme includes not only the file index, but also the user revocation set, realizing the user revocable directly. At the same time, the private key is correspondingly divided into two parts. One is the aggregation of the file index set, and the other is the aggregation of the path set for each user, so as to realize the user’s key aggregation effectively. Through the above method, only the legitimate users have access to the appropriate file, realizing the file access control function in the system effectively. This new scheme achieves the ciphertext updating through the cloud servers to save the computational overhead of data owner; when the user revocation occurs, nonrevoked user does not need to update his private key, greatly reducing the key update expensive cost and the burden of key delegate authority; because the cloud server is not completely trusted, we consider to provide a verification mechanism for the scheme, so that the data owner can validate the updated ciphertext to make sure the user revocation is carried out correctly.


## 4.2. Scheme Design

LetSetup′ be the Setup algorithm for a multilinear map, where outputs group with order p, respectively. Let T be a full binary tree with depth d(1≤d≤n), where the leaf stands for user. Number all the nodes in T from one to 2d-1; then our scheme consists of the following algorithms:(1)
Setup1λ,n: take as input the length n of index. Let {0,1}n∖{0n} be the index space. Therefore the maximum number of files in the system is N=2n-1. Let n be the all-ones vector with length n+1. Run Setup′2n to obtain the public parameters params′ for a multilinear map of target group G2n. Select a random α∈Zp, and set Xl=gelα(2l) for l=0,1,…,n-1, and set Xn=genα(2n+1)  for l=n. Lastly, let W=g2n2α(2n). It outputs the public parameters params=params′,{Xi}i∈{0,1,…,n},W.(2)
KeyGenparams: choose a random β∈Zp,  γ∈Zp and compute μ=gnβ,  v=gnγ, output PK=(μ,v),msk=(β,γ).(3)
EncryptPK,i,m,params: for a message m and an index i∈1,2,…,2n-1, randomly pick t1∈Zp and compute K=Wt1=g2nt1α(2n). The ciphertext is created as(2)C=c1,c2,c3=gnt1,vgnαit1,m·Wt1.(4)
Extractmsk,uid,S,params: given the user identity uid∈0,1d, make use of the CS method in the full binary tree T to get the user’s path path(uid)={yu0,…,yud}, such that yu0=root and yud=uid. Compute Puid=∏y∈path(uid)Z2n-y; then the path aggregate key Kuid=Puidβ. For the set S⊆1,2,…,2n-1, the index aggregate key is computed as KS=∏j∈SZ2n-jγ. Since S does not include 0, Z2n-j=gnα2n-j can always be retrieved from params. The user’s private key is set to SK=KS,Kuid.(5)
UpdatePK,R,C,params: for user revocation set R, compute coverR according to the CS method in subset-cover framework. For x∈coverR, compute Px=gnαx. Choose a random t2∈Zp; then get c3′=c3·Wt2=m·Wt1+t2. Suppose that t=t1+t2; then we have c3′=m·Wt. Compute c4=gnt2, c5=μPxt2x∈cover(R). Finally get the updated ciphertext as follows:(3)C′=c1,c2,c3′,c4,c5=gnt1,vgnαit1,m·Wt,gnt2,μPxt2x∈coverR.(6)
DecryptC,SK,S,i,R,params: when user receives the ciphertext C with the index i, if either the index i∉S or the user’s identity uid∈R, then return ⊥. Otherwise, for x=path(uid)∩coverR, decryption can be done as follows:(4)m=c3·eKS·∏j∈S,j≠iZ2n-j+i,c1e∏j∈SZ2n-j,c2·eKuid·∏y∈pathuid,y≠xZ2n-y+x,c4ePuid,c5.(7)
VerifyC,C′,PK,params: to verify whether the cloud server has executed the revocation correctly and honestly, the equation eμPx,c4=?ec5,gncan be used and it returns 0 or 1. For data owner, in order to verify whether the updated ciphertext c3′ is right or not, he can use the equation ec3′/c3,gn=?eW,c4. If returning 1, it means right or else means wrong.For correctness, we can see that (5)c3·eKS·∏j∈S,j≠iZ2n-j+i,c1e∏j∈SZ2n-j,c2·eKuid·∏y∈pathuid,y≠xZ2n-y+x,c4ePuid,c5=c3·e∏j∈SZ2n-jγ·∏j∈S,j≠iZ2n-j+i,gnt1e∏j∈SZ2n-j,vgnαit1·ePuidβ·∏y∈pathuid,y≠xZ2n-y+x,gnt2ePuid,μgnαxt2=c3·e∏j∈SZ2n-jγ,gnt1e∏j∈SZ2n-j,vt1·e∏j∈S,j≠iZ2n-j+i,gnt1e∏j∈SZ2n-j,gnαit1·ePuidβ,gnt2ePuid,μt2·e∏y∈pathuid,y≠xZ2n-y+x,gnt2e∏y∈pathuidZ2n-j,gnαxt2=c3·e∏j∈S,j≠iZ2n-j+i,gnt1e∏j∈SZ2n-j,gnαit1·e∏y∈pathuid,y≠xZ2n-y+x,gnt2e∏y∈pathuidZ2n-j,gnαxt2=m·Wt·egn∑j∈S,j≠iα2n-j+i,gnt1egn∑j∈Sα2n-j,gnαit1·egn∑y∈pathuid,y≠xα2n-y+x,gnt2egn∑y∈pathuidα2n-y,gnαxt2=m·Wtg2nα2nt1+t2=m·Wtg2nα2nt=m.


## 5. Evaluation

In this section, we evaluate the proposed scheme in two aspects, performance analysis and security analysis.


### 5.1. Performance Analysis

Performance analysis mainly includes the cost of computation, storage, and communication by comparison with several related schemes. In computation, since our scheme is based on asymmetric multilinear maps,W=g2nα(2n)in the ciphertext is system parameter, and the value of gn, gnαiand Px can be calculated in advance. Therefore, multilinear mapping operation in the process of encryption does not exist, which reduces the computational cost greatly. Decryption cost is linearly related to user’s authorized file index set and path set in the complete subtree. In terms of storage and communication cost, this paper will compare the new scheme with [3–6], including the length of system public parameters, the length of private key, length of ciphertext, revocation manners and costs, and whether it is able to verify the correctness of revocation, as shown in Table 1.Table 1
Comparison with related schemes.
Scheme
System parameter
Private key
Ciphertext
Direct revocation
Revocation cost
Verifiability
[3]
O
N
O
1
O
1
×
O
U
×
[4]
O
N
O
log
⁡
N
O
1
√
O
r
log
⁡
U
×
[5]
O
N
O
1
O
1
×
O
U
×
[6]
O
N
O
l
O
s
√
O
r
log
⁡
U
√
Our scheme
O
log
⁡
N
O
1
O
1
√
O
r
log
⁡
U
√Note that the length of ciphertext refers to the length of original ciphertext when no user has been revoked, and the revocation cost refers to the computational cost when the user revocation occurs.N stands for the maximum number of encrypted files in the system, r denotes the number of revocation users, U represents the number of legitimate users, l is number for leaf node in the access tree corresponding to the user’s private key, and s is on behalf of the number of attributes.As can be seen from Table1, the proposed scheme not only keeps the length for user’s private key as O1, but also keeps the length of the ciphertext as O1, which is as well as [3, 5] and better than [4, 6]. But the length of system parameters in [3, 5] is ON, while that in the proposed scheme is Olog⁡N. Revocation manners contain direct and indirect revocation. Direct revocation refers that the revocation list is directly embedded in the ciphertext, so that revoked users cannot decrypt any more, such as our scheme and [4, 6]; indirect revocation refers that the authorized agency or data owner distributes the updated keys for the nonrevoked users so as to realize the user revocation, such as [3, 5]. As for the revocation cost, because the indirect revocation needs to distribute updated keys to all legitimate users, computational cost for revocation is OU, while the revocation cost in our scheme and [4, 6] is mainly focused on the ciphertext update as Orlog⁡U. In addition, our scheme and [6] also provide verification mechanism, allowing the data owner and any trusted third-party auditor to verify the updated ciphertext, so as to ensure effective implementation of revocation, which is better than [3–5]. Above all, the proposed scheme is superior to [3–6], with less cost of storage and communication, and has ciphertext verifiability function.


### 5.2. Security Analysis

Our scheme is based on Generalized DHDHE assumption and is proved to be adaptive IND-CPA security under the standard model. First we analyze Generalized DHDHE assumption. LetXl=gelα(2l) for l=0,1,…,n-1, so as j∈[0,2n-1],  Zj=gnαj can be directly calculated. And given Xn=genα(2n+1), when j∈[2n+1,2n+1], Zj can be computed out. However, from Xi, Y1, and Y2, it is difficult to compute K=g2ntα(2n). The reason is that only the random t is related to Y1 and Y2. In order to obtain K, we first need to multiply Y1 and Y2, and let the multiplication results do the match operation with gnα(2n). In other words, it is necessary to calculate gnα(2n) from Xl. Since n is a n+1-dimensional vector composed of 1, any Xl cannot match with itself, which means that we can only compute gnα(2n) in the form of eΧ0s0,Χ1s1,…,Χnsn for sl∈0,1 and Χl0=gel. Notice that the index of the given Xn=genα(2n+1) is greater than α(2n), so to calculate gnα(2n), it should meet sn=0 in eΧ0s0,Χ1s1,…,Χnsn. So, gn∏l∈Lα(2l)can be obtained for L⊆[0,n-1]. However, for all the subsets of L⊆[0,n-1], there are ∑l∈L2l<2n. Therefore it is unable to calculate gnα(2n); it also means that assumption is difficult.By the following theorem, we prove the security of the proposed scheme.Theorem 5.
If the Generalized DHDHE problem is hard to solve, then the proposed revocable key-aggregate encryption scheme is selective IND-CPA security.Proof.
Assume there exists a polynomial-time adversaryA who can break the selective IND-CPA security of the revocable key-aggregate encryption scheme; then a challenger Chal can use the adversary’s ability to construct an algorithm B to solve the Generalized DHDHE problem. It is contradictory to our assumption that Generalized DHDHE problem is difficult to solve, thus proving the proposed scheme is selective IND-CPA security.
Suppose, in an asymmetric multilinear maps group system,B is given an instance of the Generalized DHDHE problem params′,{Xi}i∈{0,1,…,n},Y1,Y2,K as follows: (1)
params′←Setup′(2n), where n is the all-ones vector of length n+1.(2)
Forα∈RΖp, let Xl=gelα(2l)for l=0,1,…,n-1; and let Xn=genα(2n+1) for l=n.(3)
Fort1∈RΖp,  t2∈RΖp,  t=t1+t2, let Y1=gnt1,  Y2=gnt2.(4)
K=g2ntα(2n)or K is a random group element in G2n.
AlgorithmB decides whether K=g2ntα(2n); if it holds, it outputs 1 or else outputs 0. Algorithm B proceeds the following game with the adversary A.Init. Algorithm B initials a full binary tree T of depth d(1≤d≤n), and all the node in T is numbered from 1 to 2d-1. A submits an index i∗, R∗ that A will challenge.Setup. Algorithm B performs the following operations:(i)
Step1: it chooses a random r∈RZp and sets v=gnr/Zi∗, of which Zi∗ can be calculated by Xl. Therefore, γ=r-αi∗. Since r is randomly selected in Zp, it is independent with α. Then, according to the principle of subset-cover framework, coverR∗ can be obtained from R∗. For any xk∗∈coverR∗, it chooses a random φk∈Zp and sets μ=gnφk/Zxk∗, of which Ζxk∗ can be calculated by Xl. Therefore, β=φk-αxk∗. As φk is randomly selected in Ζp, it is independent with α. The public key is set as PK=(μ,v); note that algorithm B does not know the master secret key(β,γ).(ii)
Step2: it computes W′=e(ge0,ge1,…,gen-2,Xn-1,gen); then W=e(W′,W′)=g2nα2n.(iii)
Step3: it sends the public parameters {Xi}i∈{0,1,…,n},W and the public key PK to the adversaryA.Phase
1. A is allowed to query for private keys in this stage. For set S in condition that i∗∉S,B computes the index aggregate key KS=∏j∈SZ2n-jr/∏j∈SZ2n-j+i∗. For user identity uid∈R∗, it satisfies the condition that pathuid∩coverR∗=ϕ. So for xk∗∈coverR∗, it is bound to meet xk∗∉pathuid. From the full binary tree T, user path is denoted as path(uid)={yu0,…,yud}, such that yu0=root and yud=uid. B computes Puid=∏y∈path(uid)Z2n-y; then the path aggregate key Kuid=Puidφk/∏y∈path(uid)Z2n-y+xk∗, and SK=(KS,Kuid) will be sent to A as the answer to query. Notice that (6)KS=gnr∑j∈Sα2n-j-∑j∈Sα2n-j+i∗=gnγ∑j∈Sα2n-j+αi∗∑j∈Sα2n-j-∑j∈Sα2n-j+i∗=gnγ∑j∈Sα2n-j=∏j∈SZ2n-jγ,Kuid=gnφk∑y∈pathuidα2n-y-∑y∈pathuidα2n-y+xk∗=gnβ∑y∈pathuidα2n-y+αxk∗∑y∈pathuidα2n-y-∑y∈pathuidα2n-y+xk∗=gnβ∑y∈pathuidα2n-y=∏y∈pathuidZ2n-yβ=Puidβ.Challenge. When A ends Phase 1, it will submit two equal-length messages m0,m1∈M to algorithm B. B works as follows: (i)
Step1: it flips a random coin and marks the result as b for b∈0,1 and sets c3∗=K·mb.(ii)
Step2: it sets c1∗=Y1=gnt1, computes c2∗=Y1r, and observes that c2∗=Y1r=gnt1r=gnt1γ+αi∗.(iii)
Step3: it sets c4∗=Y2=gnt2, computes c5∗=Yφkxk∗∈coverR∗, and notices that (7)c5∗=Y2φkxk∗∈coverR∗=gnt2φkxk∗∈coverR∗=gnt2β+αxk∗xk∗∈coverR∗.(iv)
Step4: it sets the challenge ciphertext C∗=c1∗,c2∗,c3∗,c4∗,c5∗ and sends C∗ to A.Phase  2. Similarly to Phase 1, A follows the constraints of the game and continues to query about private keys; algorithm B adopts the same strategy as in Phase 1 to answer the series of queries.Guess.
A outputs a bit b′. If b′=b, algorithm B outputs 1, which means K=g2ntα(2n). Otherwise, B outputs 0 meaning that K is a random group element of G2n.Probability analysis: whenK=g2ntα(2n), the challenge ciphertext C∗=c1∗,c2∗,c3∗,c4∗,c5∗ is encrypted of the message mb. Otherwise, C∗=c1∗,c2∗,c3∗,c4∗,c5∗ is encrypted by a random element from the group G2n. In such case, the advantage of the adversary A (i.e., the probability of b′=b) is equal to 1/2. Above all, the obtained advantage of A for the proposed scheme is AdvARKAC=Pr[b′=b]-1/2=1/2±ε-1/2=ε; namely, the advantage of A to break the scheme is negligible, which indicates the revocable key-aggregate encryption scheme with selective IND-CPA security.


## 5.1. Performance Analysis

Performance analysis mainly includes the cost of computation, storage, and communication by comparison with several related schemes. In computation, since our scheme is based on asymmetric multilinear maps,W=g2nα(2n)in the ciphertext is system parameter, and the value of gn, gnαiand Px can be calculated in advance. Therefore, multilinear mapping operation in the process of encryption does not exist, which reduces the computational cost greatly. Decryption cost is linearly related to user’s authorized file index set and path set in the complete subtree. In terms of storage and communication cost, this paper will compare the new scheme with [3–6], including the length of system public parameters, the length of private key, length of ciphertext, revocation manners and costs, and whether it is able to verify the correctness of revocation, as shown in Table 1.Table 1
Comparison with related schemes.
Scheme
System parameter
Private key
Ciphertext
Direct revocation
Revocation cost
Verifiability
[3]
O
N
O
1
O
1
×
O
U
×
[4]
O
N
O
log
⁡
N
O
1
√
O
r
log
⁡
U
×
[5]
O
N
O
1
O
1
×
O
U
×
[6]
O
N
O
l
O
s
√
O
r
log
⁡
U
√
Our scheme
O
log
⁡
N
O
1
O
1
√
O
r
log
⁡
U
√Note that the length of ciphertext refers to the length of original ciphertext when no user has been revoked, and the revocation cost refers to the computational cost when the user revocation occurs.N stands for the maximum number of encrypted files in the system, r denotes the number of revocation users, U represents the number of legitimate users, l is number for leaf node in the access tree corresponding to the user’s private key, and s is on behalf of the number of attributes.As can be seen from Table1, the proposed scheme not only keeps the length for user’s private key as O1, but also keeps the length of the ciphertext as O1, which is as well as [3, 5] and better than [4, 6]. But the length of system parameters in [3, 5] is ON, while that in the proposed scheme is Olog⁡N. Revocation manners contain direct and indirect revocation. Direct revocation refers that the revocation list is directly embedded in the ciphertext, so that revoked users cannot decrypt any more, such as our scheme and [4, 6]; indirect revocation refers that the authorized agency or data owner distributes the updated keys for the nonrevoked users so as to realize the user revocation, such as [3, 5]. As for the revocation cost, because the indirect revocation needs to distribute updated keys to all legitimate users, computational cost for revocation is OU, while the revocation cost in our scheme and [4, 6] is mainly focused on the ciphertext update as Orlog⁡U. In addition, our scheme and [6] also provide verification mechanism, allowing the data owner and any trusted third-party auditor to verify the updated ciphertext, so as to ensure effective implementation of revocation, which is better than [3–5]. Above all, the proposed scheme is superior to [3–6], with less cost of storage and communication, and has ciphertext verifiability function.


## 5.2. Security Analysis

Our scheme is based on Generalized DHDHE assumption and is proved to be adaptive IND-CPA security under the standard model. First we analyze Generalized DHDHE assumption. LetXl=gelα(2l) for l=0,1,…,n-1, so as j∈[0,2n-1],  Zj=gnαj can be directly calculated. And given Xn=genα(2n+1), when j∈[2n+1,2n+1], Zj can be computed out. However, from Xi, Y1, and Y2, it is difficult to compute K=g2ntα(2n). The reason is that only the random t is related to Y1 and Y2. In order to obtain K, we first need to multiply Y1 and Y2, and let the multiplication results do the match operation with gnα(2n). In other words, it is necessary to calculate gnα(2n) from Xl. Since n is a n+1-dimensional vector composed of 1, any Xl cannot match with itself, which means that we can only compute gnα(2n) in the form of eΧ0s0,Χ1s1,…,Χnsn for sl∈0,1 and Χl0=gel. Notice that the index of the given Xn=genα(2n+1) is greater than α(2n), so to calculate gnα(2n), it should meet sn=0 in eΧ0s0,Χ1s1,…,Χnsn. So, gn∏l∈Lα(2l)can be obtained for L⊆[0,n-1]. However, for all the subsets of L⊆[0,n-1], there are ∑l∈L2l<2n. Therefore it is unable to calculate gnα(2n); it also means that assumption is difficult.By the following theorem, we prove the security of the proposed scheme.Theorem 5.
If the Generalized DHDHE problem is hard to solve, then the proposed revocable key-aggregate encryption scheme is selective IND-CPA security.Proof.
Assume there exists a polynomial-time adversaryA who can break the selective IND-CPA security of the revocable key-aggregate encryption scheme; then a challenger Chal can use the adversary’s ability to construct an algorithm B to solve the Generalized DHDHE problem. It is contradictory to our assumption that Generalized DHDHE problem is difficult to solve, thus proving the proposed scheme is selective IND-CPA security.
Suppose, in an asymmetric multilinear maps group system,B is given an instance of the Generalized DHDHE problem params′,{Xi}i∈{0,1,…,n},Y1,Y2,K as follows: (1)
params′←Setup′(2n), where n is the all-ones vector of length n+1.(2)
Forα∈RΖp, let Xl=gelα(2l)for l=0,1,…,n-1; and let Xn=genα(2n+1) for l=n.(3)
Fort1∈RΖp,  t2∈RΖp,  t=t1+t2, let Y1=gnt1,  Y2=gnt2.(4)
K=g2ntα(2n)or K is a random group element in G2n.
AlgorithmB decides whether K=g2ntα(2n); if it holds, it outputs 1 or else outputs 0. Algorithm B proceeds the following game with the adversary A.Init. Algorithm B initials a full binary tree T of depth d(1≤d≤n), and all the node in T is numbered from 1 to 2d-1. A submits an index i∗, R∗ that A will challenge.Setup. Algorithm B performs the following operations:(i)
Step1: it chooses a random r∈RZp and sets v=gnr/Zi∗, of which Zi∗ can be calculated by Xl. Therefore, γ=r-αi∗. Since r is randomly selected in Zp, it is independent with α. Then, according to the principle of subset-cover framework, coverR∗ can be obtained from R∗. For any xk∗∈coverR∗, it chooses a random φk∈Zp and sets μ=gnφk/Zxk∗, of which Ζxk∗ can be calculated by Xl. Therefore, β=φk-αxk∗. As φk is randomly selected in Ζp, it is independent with α. The public key is set as PK=(μ,v); note that algorithm B does not know the master secret key(β,γ).(ii)
Step2: it computes W′=e(ge0,ge1,…,gen-2,Xn-1,gen); then W=e(W′,W′)=g2nα2n.(iii)
Step3: it sends the public parameters {Xi}i∈{0,1,…,n},W and the public key PK to the adversaryA.Phase
1. A is allowed to query for private keys in this stage. For set S in condition that i∗∉S,B computes the index aggregate key KS=∏j∈SZ2n-jr/∏j∈SZ2n-j+i∗. For user identity uid∈R∗, it satisfies the condition that pathuid∩coverR∗=ϕ. So for xk∗∈coverR∗, it is bound to meet xk∗∉pathuid. From the full binary tree T, user path is denoted as path(uid)={yu0,…,yud}, such that yu0=root and yud=uid. B computes Puid=∏y∈path(uid)Z2n-y; then the path aggregate key Kuid=Puidφk/∏y∈path(uid)Z2n-y+xk∗, and SK=(KS,Kuid) will be sent to A as the answer to query. Notice that (6)KS=gnr∑j∈Sα2n-j-∑j∈Sα2n-j+i∗=gnγ∑j∈Sα2n-j+αi∗∑j∈Sα2n-j-∑j∈Sα2n-j+i∗=gnγ∑j∈Sα2n-j=∏j∈SZ2n-jγ,Kuid=gnφk∑y∈pathuidα2n-y-∑y∈pathuidα2n-y+xk∗=gnβ∑y∈pathuidα2n-y+αxk∗∑y∈pathuidα2n-y-∑y∈pathuidα2n-y+xk∗=gnβ∑y∈pathuidα2n-y=∏y∈pathuidZ2n-yβ=Puidβ.Challenge. When A ends Phase 1, it will submit two equal-length messages m0,m1∈M to algorithm B. B works as follows: (i)
Step1: it flips a random coin and marks the result as b for b∈0,1 and sets c3∗=K·mb.(ii)
Step2: it sets c1∗=Y1=gnt1, computes c2∗=Y1r, and observes that c2∗=Y1r=gnt1r=gnt1γ+αi∗.(iii)
Step3: it sets c4∗=Y2=gnt2, computes c5∗=Yφkxk∗∈coverR∗, and notices that (7)c5∗=Y2φkxk∗∈coverR∗=gnt2φkxk∗∈coverR∗=gnt2β+αxk∗xk∗∈coverR∗.(iv)
Step4: it sets the challenge ciphertext C∗=c1∗,c2∗,c3∗,c4∗,c5∗ and sends C∗ to A.Phase  2. Similarly to Phase 1, A follows the constraints of the game and continues to query about private keys; algorithm B adopts the same strategy as in Phase 1 to answer the series of queries.Guess.
A outputs a bit b′. If b′=b, algorithm B outputs 1, which means K=g2ntα(2n). Otherwise, B outputs 0 meaning that K is a random group element of G2n.Probability analysis: whenK=g2ntα(2n), the challenge ciphertext C∗=c1∗,c2∗,c3∗,c4∗,c5∗ is encrypted of the message mb. Otherwise, C∗=c1∗,c2∗,c3∗,c4∗,c5∗ is encrypted by a random element from the group G2n. In such case, the advantage of the adversary A (i.e., the probability of b′=b) is equal to 1/2. Above all, the obtained advantage of A for the proposed scheme is AdvARKAC=Pr[b′=b]-1/2=1/2±ε-1/2=ε; namely, the advantage of A to break the scheme is negligible, which indicates the revocable key-aggregate encryption scheme with selective IND-CPA security.


## 6. Extension

As is known to us, the number of files may extremely be large and grow rapidly in cloud scenario. If the number of files exceedsN, which is the maximum number of files setting in the system, the whole system should be reestablished in our basic scheme. So how to reduce such burden is an important issue. Inspired by the thought of public key extension in the scheme [24], we propose an extended scheme to solve the problem. We attempt to label every file with a two-level index i,j1≤i≤h,1≤j≤2n-1. When the number of files is more than N, we increase i by one and run the Extend algorithm to generate a new key-pair, adding to the original key-pair (PK,msk). That is to say, the number of files is increased by N once we obtain a new key-pair. Thus we can extend our basic scheme using this technique. The details of how to extend our basic scheme is shown as below.The Setup, KeyGen, Update, and Verify algorithm are the same as the basic scheme.E
x
t
e
n
d
μ
h
,
β
h: choose a random γh+1∈Zp and compute vh+1=gnγh+1 and output vh+1=v1,v2,…,vh+1 as a part of PK and γh+1=γ1,γ2,…,γh+1 as a part of msk.EncryptPK,a,b,m,params: for a message m and an index a,b1≤a≤h,1≤b≤2n-1, randomly pick t1∈Zp and compute c2=vagnαbt1 and c1,c3 are computed by the same way as the basic scheme.Extractmsk,uid,Sh,params: the path aggregate key Kuid remains the same as the basic scheme. For the set Sh=i,j1≤i≤h,1≤j≤2n-1, the index aggregate key is computed as KSh=∏1,j∈ShZ2n-jγ1,∏2,j∈ShZ2n-jγ2,…,∏h,j∈ShZ2n-jγh, denoted as KSh=k1,k2,…,kh.D
e
c
r
y
p
t
C
,
S
K
,
S
h
,
a
,
b
,
R
,
p
a
r
a
m
s: if either the index a,b∉Sh or the user’s identity uid∈R, then return ⊥. Otherwise, for x=path(uid)∩coverR, decryption can be done as follows:(8)m=c3·eka·∏a,j∈Sh,j≠bZ2n-j+b,c1e∏a,j∈ShZ2n-j,c2·eKuid·∏y∈pathuid,y≠xZ2n-y+x,c4ePuid,c5.The correctness of this equation can be verified after computation and therefore is omitted. The security of this extended scheme can be proved as the similar method as the basic scheme, so we do not explain it in detail here.


## 7. Conclusion and Future Work

In the cloud storage environment, in order to protect the security and privacy of users’ data and to simplify key management in the process of data sharing more effectively, key-aggregate cryptosystem has been put forward. It is realized under the public key cryptosystem and can aggregate the user’s private keys into a single one, greatly reducing the user’s key management cost. At the same time, the aggregation can be achieved without constraints, realizing the flexible data sharing in cloud environment. This paper mainly studies the revocable key-aggregate cryptosystem and proposes a revocable key-aggregate encryption scheme combined with the subset-cover framework in cloud environment, realizing the key aggregation and user access control effectively. By updating ciphertext via the cloud servers, the proposed scheme realizes the user permissions revocation while legitimate users do not need to update their private keys. What is more, it provides a verification mechanism to ensure user revocation is executed correctly. Performance analysis shows that, compared with the existing schemes, the proposed scheme reduces the cost of storage and transmission and realizes the user access control effectively. Security analysis shows that the proposed scheme proved to be selective CPA security based on Generalized DHDHE assumption in the standard model. Besides, an extended scheme is proposed to adapt for the cloud scenario, where the number of files is extremely large and growing rapidly.This paper also has limitations that it only considers to construct a CPA security scheme. Since there are a lot of solutions to transfer a scheme from CPA security to CCA security [31], how to construct an efficient CCA secure key-aggregate encryption scheme will be a concern. And the total number of users is predefined in our revocable scheme, which is not conducive to flexible extension of the system. Therefore, how to design a key-aggregate encryption scheme united the revocation and extensibility will be the future work. In addition, trying to use the theory to solve some security problems in the practical application environment, such as how to apply the idea of revocable key-aggregate cryptosystem in the privacy-preserving of data aggregation and realize the data integrity verification, will be one of the future research directions.



---

*Source: 2508693-2017-03-12.xml*