# Flexible, Secure, and Reliable Data Sharing Service Based on Collaboration in Multicloud Environment

Authors: Qiang Wei; Huaibin Shao; Gongxuan Zhang
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

Due to the abundant storage resources and high reliability data service of cloud computing, more individuals and enterprises are motivated to outsource their data to public cloud platform and enable legal data users to search and download what they need in the outsourced dataset. However, in “Paid Data Sharing” model, some valuable data should be encrypted before outsourcing for protecting owner’s economic benefits, which is an obstacle for flexible application. Specifically, if the owner does not know who (user) will download which data files in advance and even does not know the attributes of user, he/she has to either remain online all the time or import a trusted third party (TTP) to distribute the file decryption key to data user. Obviously, making the owner always remain online is too inflexible, and wholly depending on the security of TTP is a potential risk. In this paper, we propose a flexible, secure, and reliable data sharing scheme based on collaboration in multicloud environment. For securely and instantly providing data sharing service even if the owner is offline and without TTP, we distribute all encrypted split data/key blocks together to multiple cloud service providers (CSPs), respectively. An elaborate cryptographic protocol we designed helps the owner verify the correctness of data exchange bills, which is directly related to the owner’s economic benefits. Besides, in order to support reliable data service, the erasure-correcting code technic is exploited for tolerating multiple failures among CSPs, and we offer a secure keyword search mechanism that makes the system more close to reality. Extensive security analyses and experiments on real-world data show that our scheme is secure and efficient.


---

## Body

## 1. Introduction

With the arrival of data times, both individuals and enterprises are producing huge amount of data every day, which profoundly influences our living style. On one hand, the explosively increasing data creates the limits for data storage and data transmission; on the other hand, data has become an important productivity resource that could help users make data-driven decisions by some computational methods, such as giving optimized scheme by operational research [1, 2], giving accurate prediction by regression analysis [3], or carrying out geometrical computation [4]. Therefore, it is necessary to design an efficient data sharing model to share huge amount of data among different individuals or organizations. Obviously, cloud computing is certainly a prefect data sharing tool for its vast storage space and reliable distributed storage system.However, even if there are various advantages of cloud computing, security and privacy concerns are the primary obstacles to wide adoption [5]. In terms of data sharing, the data owner would like to outsource his/her data files to the remote public cloud servers and enable other users to find and download what they are interested in from cloud dataset. Although the security issues of data transmission have been deeply researched [6], which guarantees that the adversary is difficult to steal data privacy during transmission process, some potential risks still exist. For example, “curious” cloud service providers may steal valuable data by themselves for some economic benefits. To address such problem, a general approach is that the owner encrypts his/her data files with self-chosen keys before outsourcing [7]. But, in this case, how the owner flexibly and securely shares data with users is still not fully investigated.Previous works have proposed two kinds of encrypted cloud data sharing models.The first one is that the data owner encrypts their outsourced data with specific encryption key(s) so that only specific authorized data users could access and decrypt encrypted data. For example, the identity-based encryption (IBE) schemes [8, 9] and proxy-based reencryption (PRE) schemes [10, 11] enable the owner to encrypt outsourced data based on the users’ identification or their public key information. Moving a step forward, the attribute-based encryption (ABE) schemes [12, 13] could achieve a more flexible encryption model that enables data owner to encrypt data for user groups with certain attributes’ combinations instead of one specific user. The ABE has become one of the most popular methods for access control field.The second one is that the data owner directly shares the decryption key information with authorized users. This method is widely used in most searchable encryption (SE) schemes [14, 15]; it enables the owner to give the decryption key after knowing who (data user) will download which data files of him/her. Obviously, this method provides a significant advantage in “Paid Data Sharing” model (“Paid Data Sharing” model: users should pay for the downloaded data files according to their amount and prices).Unfortunately, both methods still have some limits when utilizing them in real applications.Firstly, in real data sharing system (like 4shared.com and mymedwall.com), data owner cannot determine which outsourced data files will be downloaded by which data users (even the users’ attributes) before outsourcing. So the solutions based on the first method like IBE, PRE, and ABE are not feasible anymore, because they need the owner to possess the specific information of users for each data file.Secondly, under the “Paid Data Sharing” model, it is unreasonable to make owner give all the decryption keys to the authorized users in system initialization phase. That is to say, if we follow the second method, the owner has to remain online all the time for users instantly obtaining corresponding decryption key(s). However, in reality, it is common that the data owner is the individual or resource-limited enterprises that find it difficult to always remain online.Aside from the two limits we mentioned above, in “Paid Data Sharing” scenario, it is significantly important to correctly record the details of each data exchange transaction (called “bill”), which is directly related to the benefits of owner. An alternative solution to address all these problems is to import a trusted third party (TTP) in the system; the TTP is responsible for storing and distributing the encryption keys to authorized users and maintaining the bills simultaneously. Obviously, there is no doubt that data confidentiality and bill correctness are both well guaranteed by TTP, even if the owner is completely offline. But the security of such solution relies wholly on the TTP; once the TTP is broken, all plaintext form of data will be leaked. Besides, it is not easy to find a trusted entity as TTP in practical network environment. The similar views have been early proposed in many previous works, such as the key escrow problem in ABE schemes: the security of these schemes depends majorly on the key authority (like our TTP), which will make the confidentiality of outsourced data at a potential security risk [12, 16]. From the above, it is necessary to design a flexible and secure data sharing scheme in “Paid Data Sharing” scenario, which supports offline data owner without TTP.In this paper, we discuss a “Paid Data Sharing” scheme that can be simply described as follows: a data owner encrypts his/her multiple data files and outsources them to public cloud platform, so that all authorized users could search what they are interested in and then pay and download them from cloud server. Finally, users decrypt downloaded encrypted data locally. Note that our scheme is more practical and flexible compared with previous works. Specifically, the owner does not know which data users (even their attributes) will download and decrypt which outsourced data files of him/her, while the owner cannot always keep online and there is no trusted third party in the system. For providing immediate data sharing service when the owner is offline, the owner needs to utilize the secret sharing approach to split and encrypt the file decryption key and then outsource the encrypted key blocks to multiple cloud service providers (denoted as CSPs hereafter). Except from decryption key, the owner also encrypts and distributes data blocks encoded with the erasure-correcting code technology in multiple CSPs, so that even if there are data losses occurring in some CSPs, the data redundancies can help to successfully recover the complete outsourced data for supporting reliable data sharing service. Meanwhile, an elaborately designed cryptographic protocol guarantees the correctness of each of data transactions (bills); if there are some entities deceiving the data owner for the bill content, this will be detected by the system as a high probability. Besides, we import a semitrusted proxy to provide a secure and efficient keyword-based query function that enables data user to search what he/she needs in outsourced data files before downloading. Our major contributions are shown as follows:(i)
For the first time, we explore the problems of such a practical data sharing scenario: the data owner does not know which data users (even the attributes) will download his/her encrypted files before data outsourcing, and the owner cannot always remain online simultaneously. Besides, there is no TTP in our system.(ii)
We design an elaborately cryptographic protocol that could guarantee the correctness of each of data exchange transactions (bills), so that the deceptive behavior from some semitrusted entities will be detected as a high probability.(iii)
Thorough security analysis and experiments on the real-world dataset show that our proposed scheme is secure and efficient.The remainder of this paper is organized as follows. In Section2, we give some necessary notations of our scheme and describe the system model, threat model, and design goals. Section 3 introduces some background knowledge so that readers could understand our later scheme easily, followed by Section 4, in which we propose the details of our scheme. And then we analyze the security and evaluate the performance of our proposed scheme in Section 5. The related works are discussed in Section 6. Finally, Section 7 covers the conclusion.


## 2. Problem Formulation

### 2.1. Notations

We first introduce some necessary notations that will make our later description convenient, shown as follows:(i)
F: the collection of m data files that would be outsourced to multiple cloud service providers, denoted as F={F1,F2,…,Fm}, where Fi,i∈{1,2,…,m}, is the ith file in the collection(ii)
Di: the encoded results for data file Fi. Assuming that (n,t) Reed-Solomon code is exploited for encoding data in our scheme, Di can be denoted as the collection of totally n blocks: Di={Di,1,…,Di,t,…,Di,n}, where Di,j,j∈{1,2,…,n}, represents the jth data block(iii)
Ci: the ciphertext form of Di: Ci={Ci,1,Ci,2,…,Di,n}(iv)
K: the encryption key collection for data file collection F: K={K1,K2,…,Km}, where Ki,i∈{1,2,…,n}, denotes the encryption key for Fi(v)
Si: the encoded results for Ki. Similar to encoding method of Di, Si={Si,1,…,Si,t,…,Si,n}, where Si,j,j∈{1,2,…,n}, represents the jth key block(vi)
Si,j∗ and Si,j∗∗: the ciphertext form of key block Si,j and the reencrypted form of key block Si,j, respectively, where Si,j∗ is encrypted by owner and Si,j∗∗ is reencrypted by CSP.(vii)
Bi: the bill for data file Fi(Ci), which consists of each transaction of Fi. The transaction generally includes the content about who download Fi(Ci) at what price(viii)
W: the dictionary whose elements are extracted distinct keywords from all data files(ix)
Q: the query sent by user, denoted as the collection of multiple query keywords(x)
TD: the trapdoor generated from Q (i.e., encrypted form of Q)


### 2.2. System Model

There are totally 4 entities involved in our secure keyword search scheme, data owner, multicloud alliance, semitrusted proxy, and data users, as illustrated in Figure1.Figure 1
The architecture of our proposed data sharing system.Data owner would like to share his/her valuable data with authorized users through public cloud platform. But he/she does not know who will download which data files before outsourcing and cannot remain online all the time. To ensure that only authorized users could use his/her outsourced data, owners will share a secret value L with all authorized data users in the initialization phase. For achieving the reliability, in the process of data upload, the owner firstly exploits the erasure-correcting code approach (like Reed-Solomon [17]) to split each data file Fi and its corresponding encryption key Ki as multiple block collection (i.e., Di and Si); then the owner encrypts Di and Si and sends encrypted data/key blocks (i.e., {Ci,j,Si,j∗}) to all cloud service providers, respectively (each CSP will receive one encrypted data block and one encrypted key block). The owner also generates a searchable encrypted index for all files and outsources them to proxy, so that users could search what they are interested in before downloading. After carrying out all above upload tasks, the data owner could be offline.Proxy is a semitrusted entity that maintains the encrypted index submitted by data owner. For improving the search efficiency, the index is an inverted list that was tailor-made for our scheme. Upon receiving query request from data user, the proxy searches on its local index and sends all identifications of encrypted data/key blocks that were included in searched results (we called these identifications "data request") to the multicloud alliance. Besides, since the proxy knows who download which outsourced data files (and their corresponding decryption key), it is also responsible for updating each bill Bi for each data file Fi(Ci) and sending corresponding bills to the data user.Multicloud alliance is composed of multiple cloud service providers (CSPs). It is responsible for storing the encrypted data blocks and encrypted key blocks. Upon receiving the data request from proxy, each CSP will firstly update the bills corresponding to encrypted data blocks it stores; then the randomly chosen t CSPs (chosen by user; the details are shown in next paragraph) reencrypt the corresponding encrypted key block with its updated bill and users public key. Finally, they send the encrypted data blocks as well as reencrypted key blocks together to the data user.Data users would like to send a search request to the semitrusted proxy. The search request includes the following 3 items: the trapdoor TD, search parameter k, and t randomly chosen identifications of CSPs, where parameter k denotes that the user needs the top-k ranked results and CSPs’ identifications represent user needs to download data blocks and key blocks from these t CSPs. After receiving corresponding encrypted data blocks and reencrypted key blocks from t CSPs, user could carry out the following three operations to recover the original plaintext form of data files: (1) with the bills sent by proxy and its secret key, user decrypts the reencrypted key blocks as their encrypted form that owner sends to CSPs (i.e., Si,j∗∗→Si,j∗); (2) with the secret value L given by owner, user decrypts the encrypted key blocks as unencrypted one (i.e., Si,j∗→Si,j); (3) with all plaintext forms of key blocks, users recover the decryption key Ki  (Ki is also regarded as decryption key because we use symmetrical encryption mechanism in the scheme) and then decrypt the encrypted data blocks and recover the plaintext form of data file Fi.


### 2.3. Threat Model

From the system model we described above, the threat model can be defined in terms of the security settings of cloud service providers and proxy as follows.Cloud service providers (CSPs) are “mixed-trusted” ones. (1) Most of them are “honest but curious” (i.e., semitrusted), which carry out the designed protocol honestly but are curious about the plaintext form of outsourced data file and even collude with the proxy for deceiving the data user in terms of bills for stealing the economic benefits of data owner. (2) A small part of them are completely trusted, which will not collude with other CSPs or the proxy for destroying the data confidentiality or the correctness of bills. Note that the threat model we set for CSPs is based on the reality that there are many companies providing cloud computing service at present, and some of them are big companies that significantly value their reputation.Proxy is “honest but curious,” which executes the designed protocol honestly but is curious about the plaintext form of outsourced index and query keywords sent by user. Besides, the proxy would like to collude with CSPs for forging the bills.Users are “honest but curious” ones who execute the designed protocol honestly but are curious about the plaintext form of outsourced data that other users downloaded. However, we assume that users do not collude with CSPs for revealing the secret value L or forging the bills, and they also would not reveal L to the proxy.


### 2.4. Design Goals

Our proposed data sharing scheme should achieve the following 4 design goals.


#### 2.4.1. Security

Under the threat model we defined above, the adversary should not obtain the additional information of data owner and data user except the message it receives in protocol. Besides, the bills that record the data sharing information also should be confirmable ones to protect the economic benefits for data owner. Specifically, there are 3 aspects of security, shown as follows:(i)
Data confidentiality: the confidentiality of each of outsourced data blocks should not be revealed by any adversary(ii)
Index/query privacy: the plaintext form of outsourced index and encrypted query keyword (trapdoor) should not be revealed by any adversary(iii)
Confirmable bills: any adversary cannot deceive data owner successfully in terms of the forging data exchange bills


#### 2.4.2. Reliability

Our scheme can provide reliable data sharing service even if the integrity of data blocks or key blocks of some CSPs is destroyed.


#### 2.4.3. Flexibility

In the premise that the owner does not know who will download which outsourced data files before data outsourcing, the proposed scheme should guarantee achieving a real-time data sharing service even if data owner is offline, that is, data owner in our scheme is flexible enough.


#### 2.4.4. Efficient

The response time of downloading the interested outsourced data files (the details of response time are shown in latter scheme) should be in an acceptable range. Namely, for the entities who do not possess abundant computational resources (like the owner, user, and proxy), the computational overhead of them should be relatively small.


## 2.1. Notations

We first introduce some necessary notations that will make our later description convenient, shown as follows:(i)
F: the collection of m data files that would be outsourced to multiple cloud service providers, denoted as F={F1,F2,…,Fm}, where Fi,i∈{1,2,…,m}, is the ith file in the collection(ii)
Di: the encoded results for data file Fi. Assuming that (n,t) Reed-Solomon code is exploited for encoding data in our scheme, Di can be denoted as the collection of totally n blocks: Di={Di,1,…,Di,t,…,Di,n}, where Di,j,j∈{1,2,…,n}, represents the jth data block(iii)
Ci: the ciphertext form of Di: Ci={Ci,1,Ci,2,…,Di,n}(iv)
K: the encryption key collection for data file collection F: K={K1,K2,…,Km}, where Ki,i∈{1,2,…,n}, denotes the encryption key for Fi(v)
Si: the encoded results for Ki. Similar to encoding method of Di, Si={Si,1,…,Si,t,…,Si,n}, where Si,j,j∈{1,2,…,n}, represents the jth key block(vi)
Si,j∗ and Si,j∗∗: the ciphertext form of key block Si,j and the reencrypted form of key block Si,j, respectively, where Si,j∗ is encrypted by owner and Si,j∗∗ is reencrypted by CSP.(vii)
Bi: the bill for data file Fi(Ci), which consists of each transaction of Fi. The transaction generally includes the content about who download Fi(Ci) at what price(viii)
W: the dictionary whose elements are extracted distinct keywords from all data files(ix)
Q: the query sent by user, denoted as the collection of multiple query keywords(x)
TD: the trapdoor generated from Q (i.e., encrypted form of Q)


## 2.2. System Model

There are totally 4 entities involved in our secure keyword search scheme, data owner, multicloud alliance, semitrusted proxy, and data users, as illustrated in Figure1.Figure 1
The architecture of our proposed data sharing system.Data owner would like to share his/her valuable data with authorized users through public cloud platform. But he/she does not know who will download which data files before outsourcing and cannot remain online all the time. To ensure that only authorized users could use his/her outsourced data, owners will share a secret value L with all authorized data users in the initialization phase. For achieving the reliability, in the process of data upload, the owner firstly exploits the erasure-correcting code approach (like Reed-Solomon [17]) to split each data file Fi and its corresponding encryption key Ki as multiple block collection (i.e., Di and Si); then the owner encrypts Di and Si and sends encrypted data/key blocks (i.e., {Ci,j,Si,j∗}) to all cloud service providers, respectively (each CSP will receive one encrypted data block and one encrypted key block). The owner also generates a searchable encrypted index for all files and outsources them to proxy, so that users could search what they are interested in before downloading. After carrying out all above upload tasks, the data owner could be offline.Proxy is a semitrusted entity that maintains the encrypted index submitted by data owner. For improving the search efficiency, the index is an inverted list that was tailor-made for our scheme. Upon receiving query request from data user, the proxy searches on its local index and sends all identifications of encrypted data/key blocks that were included in searched results (we called these identifications "data request") to the multicloud alliance. Besides, since the proxy knows who download which outsourced data files (and their corresponding decryption key), it is also responsible for updating each bill Bi for each data file Fi(Ci) and sending corresponding bills to the data user.Multicloud alliance is composed of multiple cloud service providers (CSPs). It is responsible for storing the encrypted data blocks and encrypted key blocks. Upon receiving the data request from proxy, each CSP will firstly update the bills corresponding to encrypted data blocks it stores; then the randomly chosen t CSPs (chosen by user; the details are shown in next paragraph) reencrypt the corresponding encrypted key block with its updated bill and users public key. Finally, they send the encrypted data blocks as well as reencrypted key blocks together to the data user.Data users would like to send a search request to the semitrusted proxy. The search request includes the following 3 items: the trapdoor TD, search parameter k, and t randomly chosen identifications of CSPs, where parameter k denotes that the user needs the top-k ranked results and CSPs’ identifications represent user needs to download data blocks and key blocks from these t CSPs. After receiving corresponding encrypted data blocks and reencrypted key blocks from t CSPs, user could carry out the following three operations to recover the original plaintext form of data files: (1) with the bills sent by proxy and its secret key, user decrypts the reencrypted key blocks as their encrypted form that owner sends to CSPs (i.e., Si,j∗∗→Si,j∗); (2) with the secret value L given by owner, user decrypts the encrypted key blocks as unencrypted one (i.e., Si,j∗→Si,j); (3) with all plaintext forms of key blocks, users recover the decryption key Ki  (Ki is also regarded as decryption key because we use symmetrical encryption mechanism in the scheme) and then decrypt the encrypted data blocks and recover the plaintext form of data file Fi.


## 2.3. Threat Model

From the system model we described above, the threat model can be defined in terms of the security settings of cloud service providers and proxy as follows.Cloud service providers (CSPs) are “mixed-trusted” ones. (1) Most of them are “honest but curious” (i.e., semitrusted), which carry out the designed protocol honestly but are curious about the plaintext form of outsourced data file and even collude with the proxy for deceiving the data user in terms of bills for stealing the economic benefits of data owner. (2) A small part of them are completely trusted, which will not collude with other CSPs or the proxy for destroying the data confidentiality or the correctness of bills. Note that the threat model we set for CSPs is based on the reality that there are many companies providing cloud computing service at present, and some of them are big companies that significantly value their reputation.Proxy is “honest but curious,” which executes the designed protocol honestly but is curious about the plaintext form of outsourced index and query keywords sent by user. Besides, the proxy would like to collude with CSPs for forging the bills.Users are “honest but curious” ones who execute the designed protocol honestly but are curious about the plaintext form of outsourced data that other users downloaded. However, we assume that users do not collude with CSPs for revealing the secret value L or forging the bills, and they also would not reveal L to the proxy.


## 2.4. Design Goals

Our proposed data sharing scheme should achieve the following 4 design goals.


### 2.4.1. Security

Under the threat model we defined above, the adversary should not obtain the additional information of data owner and data user except the message it receives in protocol. Besides, the bills that record the data sharing information also should be confirmable ones to protect the economic benefits for data owner. Specifically, there are 3 aspects of security, shown as follows:(i)
Data confidentiality: the confidentiality of each of outsourced data blocks should not be revealed by any adversary(ii)
Index/query privacy: the plaintext form of outsourced index and encrypted query keyword (trapdoor) should not be revealed by any adversary(iii)
Confirmable bills: any adversary cannot deceive data owner successfully in terms of the forging data exchange bills


### 2.4.2. Reliability

Our scheme can provide reliable data sharing service even if the integrity of data blocks or key blocks of some CSPs is destroyed.


### 2.4.3. Flexibility

In the premise that the owner does not know who will download which outsourced data files before data outsourcing, the proposed scheme should guarantee achieving a real-time data sharing service even if data owner is offline, that is, data owner in our scheme is flexible enough.


### 2.4.4. Efficient

The response time of downloading the interested outsourced data files (the details of response time are shown in latter scheme) should be in an acceptable range. Namely, for the entities who do not possess abundant computational resources (like the owner, user, and proxy), the computational overhead of them should be relatively small.


## 2.4.1. Security

Under the threat model we defined above, the adversary should not obtain the additional information of data owner and data user except the message it receives in protocol. Besides, the bills that record the data sharing information also should be confirmable ones to protect the economic benefits for data owner. Specifically, there are 3 aspects of security, shown as follows:(i)
Data confidentiality: the confidentiality of each of outsourced data blocks should not be revealed by any adversary(ii)
Index/query privacy: the plaintext form of outsourced index and encrypted query keyword (trapdoor) should not be revealed by any adversary(iii)
Confirmable bills: any adversary cannot deceive data owner successfully in terms of the forging data exchange bills


## 2.4.2. Reliability

Our scheme can provide reliable data sharing service even if the integrity of data blocks or key blocks of some CSPs is destroyed.


## 2.4.3. Flexibility

In the premise that the owner does not know who will download which outsourced data files before data outsourcing, the proposed scheme should guarantee achieving a real-time data sharing service even if data owner is offline, that is, data owner in our scheme is flexible enough.


## 2.4.4. Efficient

The response time of downloading the interested outsourced data files (the details of response time are shown in latter scheme) should be in an acceptable range. Namely, for the entities who do not possess abundant computational resources (like the owner, user, and proxy), the computational overhead of them should be relatively small.


## 3. Preliminaries

In this section, we briefly introduce 3 pieces of basic knowledge utilized in our proposed scheme.


### 3.1. Erasure-Correcting Code

The erasure-correcting code is utilized to tolerate multiple failures in distributed storage systems. Simply, an integrate data file can be encoded asn blocks and only t of them can recover the original data file, where t≤n. In this paper, if we store the encoded results of data file or encryption key (i.e., n data/key blocks) into n different CSPs, respectively, the original data file or encryption key can survive the failure of any n-t of the n CSPs without any data loss. As for encoding method, the widely used Reed-Solomon (RS) erasure-correcting code is utilized in our scheme; taking the (n,t) RS code as an example, we briefly give the process of encoding as follows; more details are shown in literature [17].For the data fileF, we firstly let F=(F1,F2,…,Ft), where each data block Fj,j∈{1,2,…,t}, can be regarded as an l-length column vector whose elements all belong to GF(2p). Then we randomly generate a t×n Vandermonde matrix A as the dispersal matrix; according to a sequence of elementary row transformations, matrix A can be rewritten as the form of (E∣P), where E is a t×t identity matrix and P is the secret parity generation matrix with size t×(n-t), shown as follows:(1)A=E∣P=10⋯0p11p12⋯p1n-t01⋯0p21p22⋯p2n-t⋮⋮⋱⋮⋮⋮⋱⋮00⋯1pt1pt2⋯ptn-t.With the dispersal matrixA, we can encode the original data file F as follows:(2)D=F·A=Fi·E∣P=D1,D2,…,Dt,Dt+1,…,Dn=F1,F2,…,Ft,Dt+1,…,Dn,where D are the encoded results composed with n blocks. Since A=(E∣P) is derived from a Vandermonde matrix, any t out of the n columns form an invertible matrix; that is, a t×t matrix whose t column vectors are distinct column vectors randomly sampled from D can be used to recover F.


### 3.2. Discrete Logarithm Assumption

Firstly, the discrete logarithm problem can be described as follows: forx∈Zp, given g and gx∈G, output x, where G is a multiplicative cyclic group in large prime order p and g is the generator of group G.The discrete logarithm assumption means that it is computationally infeasible to solve the discrete logarithm problem inG.


### 3.3. Bilinear Maps

Assuming thatG1,G2, and GT are three multiplicative cyclic groups of prime order p; g1 and g2 are the generators of G1 and G2, respectively. Then a bilinear map e^:G1×G2→GT satisfies the following properties:(i)
Bilinear: for any u∈G1, v∈G2, and two random numbers a,b∈Zp, e^(ua,vb)=e^(u,v)ab(ii)
Nondegenerate: e^(u,v)≠1(iii)
Computable: there is a polynomial-time algorithm for computing the map e^(u,v)


## 3.1. Erasure-Correcting Code

The erasure-correcting code is utilized to tolerate multiple failures in distributed storage systems. Simply, an integrate data file can be encoded asn blocks and only t of them can recover the original data file, where t≤n. In this paper, if we store the encoded results of data file or encryption key (i.e., n data/key blocks) into n different CSPs, respectively, the original data file or encryption key can survive the failure of any n-t of the n CSPs without any data loss. As for encoding method, the widely used Reed-Solomon (RS) erasure-correcting code is utilized in our scheme; taking the (n,t) RS code as an example, we briefly give the process of encoding as follows; more details are shown in literature [17].For the data fileF, we firstly let F=(F1,F2,…,Ft), where each data block Fj,j∈{1,2,…,t}, can be regarded as an l-length column vector whose elements all belong to GF(2p). Then we randomly generate a t×n Vandermonde matrix A as the dispersal matrix; according to a sequence of elementary row transformations, matrix A can be rewritten as the form of (E∣P), where E is a t×t identity matrix and P is the secret parity generation matrix with size t×(n-t), shown as follows:(1)A=E∣P=10⋯0p11p12⋯p1n-t01⋯0p21p22⋯p2n-t⋮⋮⋱⋮⋮⋮⋱⋮00⋯1pt1pt2⋯ptn-t.With the dispersal matrixA, we can encode the original data file F as follows:(2)D=F·A=Fi·E∣P=D1,D2,…,Dt,Dt+1,…,Dn=F1,F2,…,Ft,Dt+1,…,Dn,where D are the encoded results composed with n blocks. Since A=(E∣P) is derived from a Vandermonde matrix, any t out of the n columns form an invertible matrix; that is, a t×t matrix whose t column vectors are distinct column vectors randomly sampled from D can be used to recover F.


## 3.2. Discrete Logarithm Assumption

Firstly, the discrete logarithm problem can be described as follows: forx∈Zp, given g and gx∈G, output x, where G is a multiplicative cyclic group in large prime order p and g is the generator of group G.The discrete logarithm assumption means that it is computationally infeasible to solve the discrete logarithm problem inG.


## 3.3. Bilinear Maps

Assuming thatG1,G2, and GT are three multiplicative cyclic groups of prime order p; g1 and g2 are the generators of G1 and G2, respectively. Then a bilinear map e^:G1×G2→GT satisfies the following properties:(i)
Bilinear: for any u∈G1, v∈G2, and two random numbers a,b∈Zp, e^(ua,vb)=e^(u,v)ab(ii)
Nondegenerate: e^(u,v)≠1(iii)
Computable: there is a polynomial-time algorithm for computing the map e^(u,v)


## 4. The Proposed Scheme

In this section, we propose a feasible data sharing scheme that could achieve all the design goals we defined in Section2.4.


### 4.1. Setup

#### 4.1.1. Parameters Generation

First of all, the system generates and publishes the following parameters in initialization phase:(i)
G and GT: two multiplicative cyclic groups of prime order p, where g is the generator of G(ii)
L: one of the secret values shared between owner and users. All users have the same L(iii)
r: the other secret value shared between owner and user. Different users have different r(iv)
e^: a bilinear map G1×G1→GT. Its specific properties are shown in Section 3.3(v)
Zp∗: a set of nonzero elements in q-order integer group(vi)
H(·): a secure collision-resistant hash function that could map the message with any length into an element of Zp∗(vii)
Hb(·): a secure collision-resistant hash function that could map the exchange bill with any length into an element of G(viii)
Hl(·): a secure collision-resistant hash function that could map any element in GT into a fix length (in our scheme, the fix length is 128-bit) binary number(ix)
A: the t×n dispersal matrix used for encoding data file and encryption key


#### 4.1.2. Symmetric Key Generation

The data owner utilizes the traditional symmetric cryptographic mechanism (like AES algorithm) to encrypt each data block. Obviously, for protecting data confidentiality in “Paid Data Sharing” model, different data files (i.e., data block collection) should be encrypted with different encryption keys. Therefore, the owner generates encryption keyKi for each data file Fi. Besides, the secret values L and r are also generated in this phase (shown as the “search control” in Figure 1), where L is a isometric binary number as Ki. For example, in terms of AES algorithm, Ki and L are both 128-bit length binary numbers.


#### 4.1.3. Public/Secret Keys Generation

Upon receiving the data request from the proxy,t randomly chosen CSPs will firstly reencrypt the encrypted key blocks and then send the corresponding encrypted data blocks and reencrypted key blocks together to the user. For releasing from the heavy load of maintaining certificates produced by multiple users, we exploit the idea of identity-based encryption (IBE) to encrypt key information for user. Specifically, each authorized user should prepare a pair of public and secret keys, where the hash value of each user’s identification (H(uID)) is the public key and the value r·H(uID) is each user’s secret key (as we mentioned above, different users have different secret values r). Besides, each data user publishes the parameter Pu=gr in the whole system.


### 4.2. Build Index

To enable data users to search on encrypted cloud data, the data owner needs to generate a searchable index and submit it to the semitrusted proxy. The proxy maintains the index and obtains the search results for the search request sent by user according to the index. For providing efficient search, we exploit the inverted index structure widely used in many related works [18, 19] to construct index for all outsourced data files, and each term in the inverted index is the encrypted form of corresponding keyword. The specific steps for building such inverted index are shown as follows.


#### 4.2.1. Dictionary Generation

The data owner firstly needs to construct the dictionary that contains all distinct keywords extracted from all outsourcing data files. In this paper, we exploit the method proposed by Cash et al. [20] to extract keyword and then generate the dictionary W, which includes a total of 4 steps: (1) segmenting words, (2) removing stop words, (3) stemming words, and (4) merging keywords. Due to the more detailed steps shown in [20], we omit them here.


#### 4.2.2. Secure Index Construction

According to the dictionary generated above, the plaintext form of inverted index can be built by data owner. Formally, it can be shown as Table1, where w1,w2,… in the table are keywords of dictionary W; that is, the size of index is equal to the length of W. Besides, the document list in the table (i.e., F1,F3,…) represents the documents containing corresponding keyword, and the identifications of encrypted data block collections and encrypted key block collections (i.e., C1.ID,C3.ID,… and S1∗.ID,S3∗.ID,…) denote the identifications of corresponding encrypted data/key blocks stored in the multicloud alliance, where Ci.ID={Ci,1.ID,Ci,2.ID,…,Ci,n.ID} (Si∗.ID can be denoted as the similar form). In practice, the inverted index does not contain the second column “document list” of Table 1; we show it here only for easily understanding the structure of index.Table 1
The form of inverted index constructed by data owner.
Keyword Document list Identifications of encrypted data block collections Identifications of encrypted key block collections w1 F 1 , F 3 , … C1.ID,C3.ID,… S 1 ∗ . I D , S 3 ∗ . I D , … w2 F 2 , F 5 , … C2.ID,C5.ID,… S 2 ∗ . I D , S 5 ∗ . I D , … … … … …After constructing the plaintext form of inverted index, in order to protect the index privacy, owner should encrypt the keywords in the index before outsourcing them to semitrusted proxy. We design an efficient encryption algorithm based on the assumption that the discrete logarithm problem in large prime order cyclic group is difficult (the detailed explanation is shown in Section3.2). The specific encryption approach is shown as follows:(3)w∗=gHL∥wmodp-1,where w∗ represents the ciphertext form of keyword w,g and H(·) are public parameters generated in system initialization phase (see Section 4.1.1), L is the secret value shared between owner and all users, and the operator “∥” denotes cascade. Note that the encrypted index only replaces the plaintext form of keywords with encrypted keywords, but the block list and the structure of index do not change at all.Finally, data owner outsources the encrypted inverted index (denoted asI) generated above to the proxy.


### 4.3. Upload Encrypted Data/Key Blocks

Now we show how the data owner generates and uploads his/her data blocks and key blocks to the multicloud alliance.


#### 4.3.1. Encrypted Data Blocks Generation

For providing the reliable and secure data sharing service, before outsourcing the data file to CSPs, we should encode and encrypt each original data file based on erasure-correcting code approach, so that our system could tolerate multiple failures (i.e., the data integrities of some CSPs in the multicloud alliance are destroyed). In our scheme, we utilized the(n,t) Reed-Solomon erasure-correcting code for data file encoding, where t<n and n is the total number of CSPs in the multicloud alliance (according to the principle of RS code, the parameters t and n should satisfy t≤n, but t=n means that user could recover the integrated data file if and only if there is no data loss of all CSPs. Therefore, for tolerating multiple failures in multicloud alliance, we let t<n).Firstly, we generate plaintext form ofn data blocks for each data file Fi in the file collection F; the specific calculation steps are the same as (2); we directly give the encoded result Di for Fi as follows:(4)Di=Fi·A=Di,1,Di,2,…,Di,t,Di,t+1,…,Di,n.Secondly, in order to protect the data confidentiality, data owner should encrypt all data block collections with corresponding encryption keyKi. In this paper, the encryption approach we utilized is the traditional AES algorithm, and the encrypted results of Di are denoted as Ci:(5)Di→KiAESCi=Ci,1,Ci,2,…,Ci,n.For each data file that needs to be outsourced, the owner encodes it and encrypts it as (4) and (5) show and then uploads all the m (i.e., the number of data files) encrypted data block collections {C1,C2,…,Cm} to the multicloud alliance, where each data block collection is composed of n data blocks; they should be randomly dispersed to n CSPs, respectively.


#### 4.3.2. Encrypted Key Blocks Generation

In a similar way, we can also encode the encryption keyKi as n key blocks. However, since we use the AES algorithm for encrypting, Ki is only a 128-bit binary number that is not easily encoded. We will first split all Ki,i∈{1,2,…,m}, as t isometric binary number based on the XOR approach. Specifically, we randomly choose t-1 128-bit length binary vectors, denoted as {Ki,1,Ki,2,…,Ki,t-1}; then the tth key blocks can be calculated as follows:(6)Ki,t=Ki,1⊕Ki,2⊕⋯⊕Ki,t-1⊕Ki.Obviously, we can recoverKi if and only if we possess all these t blocks.Then we utilize the RS code to add(n-t) redundant isometric binary number, shown as follows:(7)Si=Ki,1,Ki,2,…,Ki,t-1,Ki,t·A=Si,1,Si,2,…,Si,t,Si,t+1,…,Si,n,where Si is a collection that contains n key blocks and any t blocks of them could be used to recover the original t key blocks we generated in (6).Finally, the owner encrypts alln key blocks of each Si as (8) and randomly disperses them to n CSPs, respectively, as the upload process of data blocks:(8)Si,t∗=Si,t⊕L.The whole process of uploading encrypted data/key blocks is shown as Algorithm1.Algorithm 1: Upload(F,K,L).
Input: the outsourced data file collection F; the encryption key collection K; the secret binary number L. Output: the encrypted data/key blocks that should be outsourced to multi-cloud alliance. (1) for each data file Fi in F  do (2) the owner encode it with (n,t) - RS code: Fi→encodeDi=Di,1,Di,2,…,Di,n (3) for each data block Di,j in Di  do (4) the owner encrypts it with Ki: Di,j→KiencryptCi,j (5) end for (6) end for (7) for each encryption (decryption) key Ki in K  do (8) the owner splits Ki as t isometric binary number: Ki→splitKi,1,Ki,2,…,Ki,n (9) the owner encode it with (n,t) - RS code: Ki,1,…,Ki,n→encodeSi=Si,1,…,Si,n (10) for each key block Si,j in Si  do (11) the owner encrypts it with L: Si,j→LencryptSi,j∗=Si,j⊕L (12) end for (13) end for (14) return  {Ci,Si∗},i∈{1,2,…,m}


### 4.4. Search

When the data user would like to search what he/she needs in the outsourced dataset, he/she will first generate trapdoorTD and randomly choose t CSPs to download data. Then users send TD, k, and the t identifications of CSPs together (called search request) to the proxy. Upon receiving the search request, the proxy performs search algorithm on the outsourced inverted index I and obtains the search results. If we call the data files that possess the query keywords “target files," then, according to the structure of index I, the search results are the identifications of encrypted data/key blocks corresponding to the target files. Finally, the proxy informs multicloud alliance to send corresponding data to users based on the search results (called data request).


#### 4.4.1. Trapdoor Generation

Firstly, the data user needs to generate trapdoorTD based on several query keywords. In fact, the trapdoor consists of all encrypted query keywords. The algorithm for encrypting one query keyword wq can be shown as follows:(9)wq∗=g1+r·HL∥wqmodp,gr·HL∥wqmodp,where wq∗ is the ciphertext form of query keyword wq; from the equation above, we see it is a two-tuple, g,H(·) are public parameters the system generates in the initialization phase, L is the secret value shared between owner and all users, and r is the secret value possessed by different owners.


#### 4.4.2. Search Process

With trapdoorTD and index I, the proxy could find which encrypted index keywords in I match the encrypted query keywords in TD; then it could obtain the corresponding encrypted data/key blocks. For ranking the search results, we follow the basic principle that “more match, higher ranking"; that is to say, for one data file (i.e., encrypted data blocks), the more keywords occur in the data file and query simultaneously, the higher score the data file will obtain. For example, the data file Fi(Ci) has the keywords w1,w2, and the data file Fi′(Ci′) has the keywords w2,w3; if the trapdoor is generated from w1 and w2, then the search score of Fi(Ci) is 2 but the search score of Fi′(Ci′) is 1. According to the search score of each data file (encrypted data blocks collection), the proxy obtains identifications of the top-k results. The algorithm for determining whether a query keyword matches the index keyword is shown as follows.We assume that the proxy could recognize identification of data user who sends the search request. Taking one query keywordwq and one index keyword w as an example, if (10) holds, we say that wq matches w.(10)g1+r·HL∥wqmodp·w∗=gr·HL∥wqmodp,where wq∗ is the encrypted query keyword in the trapdoor TD and w∗ is the encrypted index keyword in I.Correctness Proof. We can prove the correctness of (10) according to (9) and (3) as follows. If wq=w,(11)g1+r·HL∥wqmodp·w∗=g1+r·HL∥wqmodp·gHL∥wqmodp-1=gr·HL∥wqmodp.After obtaining search results, the proxy sends data request tot CSPs that are randomly chosen by user. And it also sends the data exchange transaction to all n CSPs, so that all CSPs in multicloud alliance could update their self-maintained bills. Finally, the proxy updates the bills it maintained (i.e., adding the exchange transaction to corresponding bills) and sends each bill Bi that has been updated to the user. Note that these bills will be used for decrypting encryption key in latter download process (see Section 4.5).


### 4.5. Download Encrypted Data/Key Blocks

For thet randomly chosen CSPs, they will firstly update the bills corresponding to data files (i.e., encrypted data blocks) that need to be downloaded and then reencrypt corresponding encrypted key blocks with updated bills and the public key of users. Finally, they send the encrypted data blocks with reencrypted key blocks together to the user. For example, assuming that the encrypted data block collection Ci is what user needs, for one of the t CSPs that stores one of the encrypted data blocks Ci,j and encrypted key blocks Si,j, it firstly encrypts Ki,j with the bill Bi′ (For distinguishing the bills proxy sends to user and the bills CSPs maintain, we denote the bill maintained by one CSP that stored Ci,j as Bi′ and denote the bill proxy sends to user as Bi) and sends the two-tuples Ci,j,Si,j∗∗ to the user, where Si,j∗∗ is the encrypted form of key block Si,j. We follow the idea of identity-based encryption (IBE) to design the encryption/decryption algorithm for encrypted key blocks, shown as follows.


#### 4.5.1. Key Blocks Reencryption

For one of thet CSPs that store Ci,j and Si,j∗, it randomly chooses q∈Zp∗; then the CSP calculates 3 variates αi,j,μi,j, and υi,j as shown in the following equations:(12)αi,j=e^HbBi′HuID,Pu,μi,j=gq,υi,j=Si,j∗⊕Hlαi,jq,where the six parameters {e^,Hb(·),Hl(·),H(·),g,Pu} are all predefined in theSetup phase of our scheme.Note that the reencrypted form of key blockSi,j (i.e., Si,j∗∗) is denoted as the two-tuples {μi,j,υi,j} and each of t CSPs will send it together with encrypted data block Ci,j to the user. Due to different identifications, different users would receive different form of Si,j∗∗.


#### 4.5.2. Key Blocks Decryption

Upon user receiving allt encrypted key blocks (i.e., {μi,j,υi,j}) from t CSPs (here, we assume that user could identify the identifications of all t CSPs who send data), he/she could decrypt them with his/her secret key, r·H(uID), shown as follows:(13)Si,j∗=υi,j⊕Hle^HbBir·HuID,μi,j,where υi,j,μi,j are included in the encrypted form of Si,j, r is the secret value shared between owner and the user, Bi is the bill for Ci sent by the proxy, and Hl(·),Hb(·) are public parameters we prepared in ourSetup phase. Finally, user could decrypt Si,j∗ with L.(14)Si,j=Si,j∗⊕L.


#### 4.5.3. File Decryption

For obtaining plaintext form of original data fileFi, after decrypting all t encrypted key blocks, the data user could obtain the original unencrypted encryption key Ki by decoding t unencrypted key blocks with dispersal matrix A. Then user decrypts each of encrypted data blocks in Ci and decode them in the same way. Now user could obtain the plaintext form of original data file Fi. The detailed processes of searching and downloading encrypted data/key blocks are summarized in Figure 2.Figure 2
The processes of search and download encrypted data/key blocks.


### 4.6. Correctness Analysis

In this section, we will show why data user could correctly decrypt the encrypted key blocks from each CSP if and only if the two bills of one corresponding data file (i.e., the bill from proxy and the bill form CSP) are exactly equal to each other. Without loss of generality, taking the key blockSi,j as an example, according to the encryption given by (12) and the decryption process shown in (13) and (14), we can prove that Si,j could be correctly decrypted when Bi=Bi′, as shown as follows.Firstly, the reencrypted form ofSi,j(Si,j∗∗) is shown as follows:(15)Si,j∗∗=μi,j,υi,j=gq,Si,j∗⊕Hle^HbBi′HuID,Pur=gq,Si,j⊕L⊕Hle^HbBi′HuID,Pur.Secondly, if and only ifBi=Bi′, we can correctly decrypt Si,j∗, as shown as follows:(16)υi,j⊕Hle^HbBir·HuID,μi,j=Si,j∗⊕Hlαi,jq⊕Hle^HbBir·HuID,μi=Si,j∗⊕Hle^HbBi′HuID,Puq⊕Hle^HbBir·HuID,gq=Si,j∗⊕Hle^HbBi′HuID,Puq⊕Hle^HbBiHuID,Puq=Si,j∗.Obviously, if we successfully decryptSi,j∗, we can correctly decrypt Si,j∗ as secret binary number L; we omit the correctness proof here.


### 4.7. Summary of Scheme

Now we summarize our proposed scheme in terms of reliability and flexibility. The detailed analyses about security and efficiency are shown in Section5.


#### 4.7.1. Reliability

The(n,t) Reed-Solomon (RS) erasure-correcting code guarantees the reliability of our system. If there are some errors, such as data loss (key blocks or data blocks) occurring in some CSPs, the properties of erasure-correcting code could help the system to recover the complete data in time. In practice, when the owner deploys cloud services, some mature technology like virtual machines (VM) replication also could be used to enhance the data reliability, and the efficient issues like huge network resource consumption in failure recovery process have been deeply researched [21] to improve the quality of data service. That is to say, many technological means could guarantee the reliability of our system.


#### 4.7.2. Flexibility

The owner outsources the (1) encrypted data blocks, (2) encrypted key blocks, and (3) encrypted index to the multicloud alliance and proxy, respectively. Therefore, data user could search what he/she needs in outsourced cloud data and download them as well as corresponding encrypted key blocks and finally decrypt the key and data. The whole data sharing process does not need the owner to remain online after finishing the upload process. It obviously brings significant flexibility to data owner.


## 4.1. Setup

### 4.1.1. Parameters Generation

First of all, the system generates and publishes the following parameters in initialization phase:(i)
G and GT: two multiplicative cyclic groups of prime order p, where g is the generator of G(ii)
L: one of the secret values shared between owner and users. All users have the same L(iii)
r: the other secret value shared between owner and user. Different users have different r(iv)
e^: a bilinear map G1×G1→GT. Its specific properties are shown in Section 3.3(v)
Zp∗: a set of nonzero elements in q-order integer group(vi)
H(·): a secure collision-resistant hash function that could map the message with any length into an element of Zp∗(vii)
Hb(·): a secure collision-resistant hash function that could map the exchange bill with any length into an element of G(viii)
Hl(·): a secure collision-resistant hash function that could map any element in GT into a fix length (in our scheme, the fix length is 128-bit) binary number(ix)
A: the t×n dispersal matrix used for encoding data file and encryption key


### 4.1.2. Symmetric Key Generation

The data owner utilizes the traditional symmetric cryptographic mechanism (like AES algorithm) to encrypt each data block. Obviously, for protecting data confidentiality in “Paid Data Sharing” model, different data files (i.e., data block collection) should be encrypted with different encryption keys. Therefore, the owner generates encryption keyKi for each data file Fi. Besides, the secret values L and r are also generated in this phase (shown as the “search control” in Figure 1), where L is a isometric binary number as Ki. For example, in terms of AES algorithm, Ki and L are both 128-bit length binary numbers.


### 4.1.3. Public/Secret Keys Generation

Upon receiving the data request from the proxy,t randomly chosen CSPs will firstly reencrypt the encrypted key blocks and then send the corresponding encrypted data blocks and reencrypted key blocks together to the user. For releasing from the heavy load of maintaining certificates produced by multiple users, we exploit the idea of identity-based encryption (IBE) to encrypt key information for user. Specifically, each authorized user should prepare a pair of public and secret keys, where the hash value of each user’s identification (H(uID)) is the public key and the value r·H(uID) is each user’s secret key (as we mentioned above, different users have different secret values r). Besides, each data user publishes the parameter Pu=gr in the whole system.


## 4.1.1. Parameters Generation

First of all, the system generates and publishes the following parameters in initialization phase:(i)
G and GT: two multiplicative cyclic groups of prime order p, where g is the generator of G(ii)
L: one of the secret values shared between owner and users. All users have the same L(iii)
r: the other secret value shared between owner and user. Different users have different r(iv)
e^: a bilinear map G1×G1→GT. Its specific properties are shown in Section 3.3(v)
Zp∗: a set of nonzero elements in q-order integer group(vi)
H(·): a secure collision-resistant hash function that could map the message with any length into an element of Zp∗(vii)
Hb(·): a secure collision-resistant hash function that could map the exchange bill with any length into an element of G(viii)
Hl(·): a secure collision-resistant hash function that could map any element in GT into a fix length (in our scheme, the fix length is 128-bit) binary number(ix)
A: the t×n dispersal matrix used for encoding data file and encryption key


## 4.1.2. Symmetric Key Generation

The data owner utilizes the traditional symmetric cryptographic mechanism (like AES algorithm) to encrypt each data block. Obviously, for protecting data confidentiality in “Paid Data Sharing” model, different data files (i.e., data block collection) should be encrypted with different encryption keys. Therefore, the owner generates encryption keyKi for each data file Fi. Besides, the secret values L and r are also generated in this phase (shown as the “search control” in Figure 1), where L is a isometric binary number as Ki. For example, in terms of AES algorithm, Ki and L are both 128-bit length binary numbers.


## 4.1.3. Public/Secret Keys Generation

Upon receiving the data request from the proxy,t randomly chosen CSPs will firstly reencrypt the encrypted key blocks and then send the corresponding encrypted data blocks and reencrypted key blocks together to the user. For releasing from the heavy load of maintaining certificates produced by multiple users, we exploit the idea of identity-based encryption (IBE) to encrypt key information for user. Specifically, each authorized user should prepare a pair of public and secret keys, where the hash value of each user’s identification (H(uID)) is the public key and the value r·H(uID) is each user’s secret key (as we mentioned above, different users have different secret values r). Besides, each data user publishes the parameter Pu=gr in the whole system.


## 4.2. Build Index

To enable data users to search on encrypted cloud data, the data owner needs to generate a searchable index and submit it to the semitrusted proxy. The proxy maintains the index and obtains the search results for the search request sent by user according to the index. For providing efficient search, we exploit the inverted index structure widely used in many related works [18, 19] to construct index for all outsourced data files, and each term in the inverted index is the encrypted form of corresponding keyword. The specific steps for building such inverted index are shown as follows.


### 4.2.1. Dictionary Generation

The data owner firstly needs to construct the dictionary that contains all distinct keywords extracted from all outsourcing data files. In this paper, we exploit the method proposed by Cash et al. [20] to extract keyword and then generate the dictionary W, which includes a total of 4 steps: (1) segmenting words, (2) removing stop words, (3) stemming words, and (4) merging keywords. Due to the more detailed steps shown in [20], we omit them here.


### 4.2.2. Secure Index Construction

According to the dictionary generated above, the plaintext form of inverted index can be built by data owner. Formally, it can be shown as Table1, where w1,w2,… in the table are keywords of dictionary W; that is, the size of index is equal to the length of W. Besides, the document list in the table (i.e., F1,F3,…) represents the documents containing corresponding keyword, and the identifications of encrypted data block collections and encrypted key block collections (i.e., C1.ID,C3.ID,… and S1∗.ID,S3∗.ID,…) denote the identifications of corresponding encrypted data/key blocks stored in the multicloud alliance, where Ci.ID={Ci,1.ID,Ci,2.ID,…,Ci,n.ID} (Si∗.ID can be denoted as the similar form). In practice, the inverted index does not contain the second column “document list” of Table 1; we show it here only for easily understanding the structure of index.Table 1
The form of inverted index constructed by data owner.
Keyword Document list Identifications of encrypted data block collections Identifications of encrypted key block collections w1 F 1 , F 3 , … C1.ID,C3.ID,… S 1 ∗ . I D , S 3 ∗ . I D , … w2 F 2 , F 5 , … C2.ID,C5.ID,… S 2 ∗ . I D , S 5 ∗ . I D , … … … … …After constructing the plaintext form of inverted index, in order to protect the index privacy, owner should encrypt the keywords in the index before outsourcing them to semitrusted proxy. We design an efficient encryption algorithm based on the assumption that the discrete logarithm problem in large prime order cyclic group is difficult (the detailed explanation is shown in Section3.2). The specific encryption approach is shown as follows:(3)w∗=gHL∥wmodp-1,where w∗ represents the ciphertext form of keyword w,g and H(·) are public parameters generated in system initialization phase (see Section 4.1.1), L is the secret value shared between owner and all users, and the operator “∥” denotes cascade. Note that the encrypted index only replaces the plaintext form of keywords with encrypted keywords, but the block list and the structure of index do not change at all.Finally, data owner outsources the encrypted inverted index (denoted asI) generated above to the proxy.


## 4.2.1. Dictionary Generation

The data owner firstly needs to construct the dictionary that contains all distinct keywords extracted from all outsourcing data files. In this paper, we exploit the method proposed by Cash et al. [20] to extract keyword and then generate the dictionary W, which includes a total of 4 steps: (1) segmenting words, (2) removing stop words, (3) stemming words, and (4) merging keywords. Due to the more detailed steps shown in [20], we omit them here.


## 4.2.2. Secure Index Construction

According to the dictionary generated above, the plaintext form of inverted index can be built by data owner. Formally, it can be shown as Table1, where w1,w2,… in the table are keywords of dictionary W; that is, the size of index is equal to the length of W. Besides, the document list in the table (i.e., F1,F3,…) represents the documents containing corresponding keyword, and the identifications of encrypted data block collections and encrypted key block collections (i.e., C1.ID,C3.ID,… and S1∗.ID,S3∗.ID,…) denote the identifications of corresponding encrypted data/key blocks stored in the multicloud alliance, where Ci.ID={Ci,1.ID,Ci,2.ID,…,Ci,n.ID} (Si∗.ID can be denoted as the similar form). In practice, the inverted index does not contain the second column “document list” of Table 1; we show it here only for easily understanding the structure of index.Table 1
The form of inverted index constructed by data owner.
Keyword Document list Identifications of encrypted data block collections Identifications of encrypted key block collections w1 F 1 , F 3 , … C1.ID,C3.ID,… S 1 ∗ . I D , S 3 ∗ . I D , … w2 F 2 , F 5 , … C2.ID,C5.ID,… S 2 ∗ . I D , S 5 ∗ . I D , … … … … …After constructing the plaintext form of inverted index, in order to protect the index privacy, owner should encrypt the keywords in the index before outsourcing them to semitrusted proxy. We design an efficient encryption algorithm based on the assumption that the discrete logarithm problem in large prime order cyclic group is difficult (the detailed explanation is shown in Section3.2). The specific encryption approach is shown as follows:(3)w∗=gHL∥wmodp-1,where w∗ represents the ciphertext form of keyword w,g and H(·) are public parameters generated in system initialization phase (see Section 4.1.1), L is the secret value shared between owner and all users, and the operator “∥” denotes cascade. Note that the encrypted index only replaces the plaintext form of keywords with encrypted keywords, but the block list and the structure of index do not change at all.Finally, data owner outsources the encrypted inverted index (denoted asI) generated above to the proxy.


## 4.3. Upload Encrypted Data/Key Blocks

Now we show how the data owner generates and uploads his/her data blocks and key blocks to the multicloud alliance.


### 4.3.1. Encrypted Data Blocks Generation

For providing the reliable and secure data sharing service, before outsourcing the data file to CSPs, we should encode and encrypt each original data file based on erasure-correcting code approach, so that our system could tolerate multiple failures (i.e., the data integrities of some CSPs in the multicloud alliance are destroyed). In our scheme, we utilized the(n,t) Reed-Solomon erasure-correcting code for data file encoding, where t<n and n is the total number of CSPs in the multicloud alliance (according to the principle of RS code, the parameters t and n should satisfy t≤n, but t=n means that user could recover the integrated data file if and only if there is no data loss of all CSPs. Therefore, for tolerating multiple failures in multicloud alliance, we let t<n).Firstly, we generate plaintext form ofn data blocks for each data file Fi in the file collection F; the specific calculation steps are the same as (2); we directly give the encoded result Di for Fi as follows:(4)Di=Fi·A=Di,1,Di,2,…,Di,t,Di,t+1,…,Di,n.Secondly, in order to protect the data confidentiality, data owner should encrypt all data block collections with corresponding encryption keyKi. In this paper, the encryption approach we utilized is the traditional AES algorithm, and the encrypted results of Di are denoted as Ci:(5)Di→KiAESCi=Ci,1,Ci,2,…,Ci,n.For each data file that needs to be outsourced, the owner encodes it and encrypts it as (4) and (5) show and then uploads all the m (i.e., the number of data files) encrypted data block collections {C1,C2,…,Cm} to the multicloud alliance, where each data block collection is composed of n data blocks; they should be randomly dispersed to n CSPs, respectively.


### 4.3.2. Encrypted Key Blocks Generation

In a similar way, we can also encode the encryption keyKi as n key blocks. However, since we use the AES algorithm for encrypting, Ki is only a 128-bit binary number that is not easily encoded. We will first split all Ki,i∈{1,2,…,m}, as t isometric binary number based on the XOR approach. Specifically, we randomly choose t-1 128-bit length binary vectors, denoted as {Ki,1,Ki,2,…,Ki,t-1}; then the tth key blocks can be calculated as follows:(6)Ki,t=Ki,1⊕Ki,2⊕⋯⊕Ki,t-1⊕Ki.Obviously, we can recoverKi if and only if we possess all these t blocks.Then we utilize the RS code to add(n-t) redundant isometric binary number, shown as follows:(7)Si=Ki,1,Ki,2,…,Ki,t-1,Ki,t·A=Si,1,Si,2,…,Si,t,Si,t+1,…,Si,n,where Si is a collection that contains n key blocks and any t blocks of them could be used to recover the original t key blocks we generated in (6).Finally, the owner encrypts alln key blocks of each Si as (8) and randomly disperses them to n CSPs, respectively, as the upload process of data blocks:(8)Si,t∗=Si,t⊕L.The whole process of uploading encrypted data/key blocks is shown as Algorithm1.Algorithm 1: Upload(F,K,L).
Input: the outsourced data file collection F; the encryption key collection K; the secret binary number L. Output: the encrypted data/key blocks that should be outsourced to multi-cloud alliance. (1) for each data file Fi in F  do (2) the owner encode it with (n,t) - RS code: Fi→encodeDi=Di,1,Di,2,…,Di,n (3) for each data block Di,j in Di  do (4) the owner encrypts it with Ki: Di,j→KiencryptCi,j (5) end for (6) end for (7) for each encryption (decryption) key Ki in K  do (8) the owner splits Ki as t isometric binary number: Ki→splitKi,1,Ki,2,…,Ki,n (9) the owner encode it with (n,t) - RS code: Ki,1,…,Ki,n→encodeSi=Si,1,…,Si,n (10) for each key block Si,j in Si  do (11) the owner encrypts it with L: Si,j→LencryptSi,j∗=Si,j⊕L (12) end for (13) end for (14) return  {Ci,Si∗},i∈{1,2,…,m}


## 4.3.1. Encrypted Data Blocks Generation

For providing the reliable and secure data sharing service, before outsourcing the data file to CSPs, we should encode and encrypt each original data file based on erasure-correcting code approach, so that our system could tolerate multiple failures (i.e., the data integrities of some CSPs in the multicloud alliance are destroyed). In our scheme, we utilized the(n,t) Reed-Solomon erasure-correcting code for data file encoding, where t<n and n is the total number of CSPs in the multicloud alliance (according to the principle of RS code, the parameters t and n should satisfy t≤n, but t=n means that user could recover the integrated data file if and only if there is no data loss of all CSPs. Therefore, for tolerating multiple failures in multicloud alliance, we let t<n).Firstly, we generate plaintext form ofn data blocks for each data file Fi in the file collection F; the specific calculation steps are the same as (2); we directly give the encoded result Di for Fi as follows:(4)Di=Fi·A=Di,1,Di,2,…,Di,t,Di,t+1,…,Di,n.Secondly, in order to protect the data confidentiality, data owner should encrypt all data block collections with corresponding encryption keyKi. In this paper, the encryption approach we utilized is the traditional AES algorithm, and the encrypted results of Di are denoted as Ci:(5)Di→KiAESCi=Ci,1,Ci,2,…,Ci,n.For each data file that needs to be outsourced, the owner encodes it and encrypts it as (4) and (5) show and then uploads all the m (i.e., the number of data files) encrypted data block collections {C1,C2,…,Cm} to the multicloud alliance, where each data block collection is composed of n data blocks; they should be randomly dispersed to n CSPs, respectively.


## 4.3.2. Encrypted Key Blocks Generation

In a similar way, we can also encode the encryption keyKi as n key blocks. However, since we use the AES algorithm for encrypting, Ki is only a 128-bit binary number that is not easily encoded. We will first split all Ki,i∈{1,2,…,m}, as t isometric binary number based on the XOR approach. Specifically, we randomly choose t-1 128-bit length binary vectors, denoted as {Ki,1,Ki,2,…,Ki,t-1}; then the tth key blocks can be calculated as follows:(6)Ki,t=Ki,1⊕Ki,2⊕⋯⊕Ki,t-1⊕Ki.Obviously, we can recoverKi if and only if we possess all these t blocks.Then we utilize the RS code to add(n-t) redundant isometric binary number, shown as follows:(7)Si=Ki,1,Ki,2,…,Ki,t-1,Ki,t·A=Si,1,Si,2,…,Si,t,Si,t+1,…,Si,n,where Si is a collection that contains n key blocks and any t blocks of them could be used to recover the original t key blocks we generated in (6).Finally, the owner encrypts alln key blocks of each Si as (8) and randomly disperses them to n CSPs, respectively, as the upload process of data blocks:(8)Si,t∗=Si,t⊕L.The whole process of uploading encrypted data/key blocks is shown as Algorithm1.Algorithm 1: Upload(F,K,L).
Input: the outsourced data file collection F; the encryption key collection K; the secret binary number L. Output: the encrypted data/key blocks that should be outsourced to multi-cloud alliance. (1) for each data file Fi in F  do (2) the owner encode it with (n,t) - RS code: Fi→encodeDi=Di,1,Di,2,…,Di,n (3) for each data block Di,j in Di  do (4) the owner encrypts it with Ki: Di,j→KiencryptCi,j (5) end for (6) end for (7) for each encryption (decryption) key Ki in K  do (8) the owner splits Ki as t isometric binary number: Ki→splitKi,1,Ki,2,…,Ki,n (9) the owner encode it with (n,t) - RS code: Ki,1,…,Ki,n→encodeSi=Si,1,…,Si,n (10) for each key block Si,j in Si  do (11) the owner encrypts it with L: Si,j→LencryptSi,j∗=Si,j⊕L (12) end for (13) end for (14) return  {Ci,Si∗},i∈{1,2,…,m}


## 4.4. Search

When the data user would like to search what he/she needs in the outsourced dataset, he/she will first generate trapdoorTD and randomly choose t CSPs to download data. Then users send TD, k, and the t identifications of CSPs together (called search request) to the proxy. Upon receiving the search request, the proxy performs search algorithm on the outsourced inverted index I and obtains the search results. If we call the data files that possess the query keywords “target files," then, according to the structure of index I, the search results are the identifications of encrypted data/key blocks corresponding to the target files. Finally, the proxy informs multicloud alliance to send corresponding data to users based on the search results (called data request).


### 4.4.1. Trapdoor Generation

Firstly, the data user needs to generate trapdoorTD based on several query keywords. In fact, the trapdoor consists of all encrypted query keywords. The algorithm for encrypting one query keyword wq can be shown as follows:(9)wq∗=g1+r·HL∥wqmodp,gr·HL∥wqmodp,where wq∗ is the ciphertext form of query keyword wq; from the equation above, we see it is a two-tuple, g,H(·) are public parameters the system generates in the initialization phase, L is the secret value shared between owner and all users, and r is the secret value possessed by different owners.


### 4.4.2. Search Process

With trapdoorTD and index I, the proxy could find which encrypted index keywords in I match the encrypted query keywords in TD; then it could obtain the corresponding encrypted data/key blocks. For ranking the search results, we follow the basic principle that “more match, higher ranking"; that is to say, for one data file (i.e., encrypted data blocks), the more keywords occur in the data file and query simultaneously, the higher score the data file will obtain. For example, the data file Fi(Ci) has the keywords w1,w2, and the data file Fi′(Ci′) has the keywords w2,w3; if the trapdoor is generated from w1 and w2, then the search score of Fi(Ci) is 2 but the search score of Fi′(Ci′) is 1. According to the search score of each data file (encrypted data blocks collection), the proxy obtains identifications of the top-k results. The algorithm for determining whether a query keyword matches the index keyword is shown as follows.We assume that the proxy could recognize identification of data user who sends the search request. Taking one query keywordwq and one index keyword w as an example, if (10) holds, we say that wq matches w.(10)g1+r·HL∥wqmodp·w∗=gr·HL∥wqmodp,where wq∗ is the encrypted query keyword in the trapdoor TD and w∗ is the encrypted index keyword in I.Correctness Proof. We can prove the correctness of (10) according to (9) and (3) as follows. If wq=w,(11)g1+r·HL∥wqmodp·w∗=g1+r·HL∥wqmodp·gHL∥wqmodp-1=gr·HL∥wqmodp.After obtaining search results, the proxy sends data request tot CSPs that are randomly chosen by user. And it also sends the data exchange transaction to all n CSPs, so that all CSPs in multicloud alliance could update their self-maintained bills. Finally, the proxy updates the bills it maintained (i.e., adding the exchange transaction to corresponding bills) and sends each bill Bi that has been updated to the user. Note that these bills will be used for decrypting encryption key in latter download process (see Section 4.5).


## 4.4.1. Trapdoor Generation

Firstly, the data user needs to generate trapdoorTD based on several query keywords. In fact, the trapdoor consists of all encrypted query keywords. The algorithm for encrypting one query keyword wq can be shown as follows:(9)wq∗=g1+r·HL∥wqmodp,gr·HL∥wqmodp,where wq∗ is the ciphertext form of query keyword wq; from the equation above, we see it is a two-tuple, g,H(·) are public parameters the system generates in the initialization phase, L is the secret value shared between owner and all users, and r is the secret value possessed by different owners.


## 4.4.2. Search Process

With trapdoorTD and index I, the proxy could find which encrypted index keywords in I match the encrypted query keywords in TD; then it could obtain the corresponding encrypted data/key blocks. For ranking the search results, we follow the basic principle that “more match, higher ranking"; that is to say, for one data file (i.e., encrypted data blocks), the more keywords occur in the data file and query simultaneously, the higher score the data file will obtain. For example, the data file Fi(Ci) has the keywords w1,w2, and the data file Fi′(Ci′) has the keywords w2,w3; if the trapdoor is generated from w1 and w2, then the search score of Fi(Ci) is 2 but the search score of Fi′(Ci′) is 1. According to the search score of each data file (encrypted data blocks collection), the proxy obtains identifications of the top-k results. The algorithm for determining whether a query keyword matches the index keyword is shown as follows.We assume that the proxy could recognize identification of data user who sends the search request. Taking one query keywordwq and one index keyword w as an example, if (10) holds, we say that wq matches w.(10)g1+r·HL∥wqmodp·w∗=gr·HL∥wqmodp,where wq∗ is the encrypted query keyword in the trapdoor TD and w∗ is the encrypted index keyword in I.Correctness Proof. We can prove the correctness of (10) according to (9) and (3) as follows. If wq=w,(11)g1+r·HL∥wqmodp·w∗=g1+r·HL∥wqmodp·gHL∥wqmodp-1=gr·HL∥wqmodp.After obtaining search results, the proxy sends data request tot CSPs that are randomly chosen by user. And it also sends the data exchange transaction to all n CSPs, so that all CSPs in multicloud alliance could update their self-maintained bills. Finally, the proxy updates the bills it maintained (i.e., adding the exchange transaction to corresponding bills) and sends each bill Bi that has been updated to the user. Note that these bills will be used for decrypting encryption key in latter download process (see Section 4.5).


## 4.5. Download Encrypted Data/Key Blocks

For thet randomly chosen CSPs, they will firstly update the bills corresponding to data files (i.e., encrypted data blocks) that need to be downloaded and then reencrypt corresponding encrypted key blocks with updated bills and the public key of users. Finally, they send the encrypted data blocks with reencrypted key blocks together to the user. For example, assuming that the encrypted data block collection Ci is what user needs, for one of the t CSPs that stores one of the encrypted data blocks Ci,j and encrypted key blocks Si,j, it firstly encrypts Ki,j with the bill Bi′ (For distinguishing the bills proxy sends to user and the bills CSPs maintain, we denote the bill maintained by one CSP that stored Ci,j as Bi′ and denote the bill proxy sends to user as Bi) and sends the two-tuples Ci,j,Si,j∗∗ to the user, where Si,j∗∗ is the encrypted form of key block Si,j. We follow the idea of identity-based encryption (IBE) to design the encryption/decryption algorithm for encrypted key blocks, shown as follows.


### 4.5.1. Key Blocks Reencryption

For one of thet CSPs that store Ci,j and Si,j∗, it randomly chooses q∈Zp∗; then the CSP calculates 3 variates αi,j,μi,j, and υi,j as shown in the following equations:(12)αi,j=e^HbBi′HuID,Pu,μi,j=gq,υi,j=Si,j∗⊕Hlαi,jq,where the six parameters {e^,Hb(·),Hl(·),H(·),g,Pu} are all predefined in theSetup phase of our scheme.Note that the reencrypted form of key blockSi,j (i.e., Si,j∗∗) is denoted as the two-tuples {μi,j,υi,j} and each of t CSPs will send it together with encrypted data block Ci,j to the user. Due to different identifications, different users would receive different form of Si,j∗∗.


### 4.5.2. Key Blocks Decryption

Upon user receiving allt encrypted key blocks (i.e., {μi,j,υi,j}) from t CSPs (here, we assume that user could identify the identifications of all t CSPs who send data), he/she could decrypt them with his/her secret key, r·H(uID), shown as follows:(13)Si,j∗=υi,j⊕Hle^HbBir·HuID,μi,j,where υi,j,μi,j are included in the encrypted form of Si,j, r is the secret value shared between owner and the user, Bi is the bill for Ci sent by the proxy, and Hl(·),Hb(·) are public parameters we prepared in ourSetup phase. Finally, user could decrypt Si,j∗ with L.(14)Si,j=Si,j∗⊕L.


### 4.5.3. File Decryption

For obtaining plaintext form of original data fileFi, after decrypting all t encrypted key blocks, the data user could obtain the original unencrypted encryption key Ki by decoding t unencrypted key blocks with dispersal matrix A. Then user decrypts each of encrypted data blocks in Ci and decode them in the same way. Now user could obtain the plaintext form of original data file Fi. The detailed processes of searching and downloading encrypted data/key blocks are summarized in Figure 2.Figure 2
The processes of search and download encrypted data/key blocks.


## 4.5.1. Key Blocks Reencryption

For one of thet CSPs that store Ci,j and Si,j∗, it randomly chooses q∈Zp∗; then the CSP calculates 3 variates αi,j,μi,j, and υi,j as shown in the following equations:(12)αi,j=e^HbBi′HuID,Pu,μi,j=gq,υi,j=Si,j∗⊕Hlαi,jq,where the six parameters {e^,Hb(·),Hl(·),H(·),g,Pu} are all predefined in theSetup phase of our scheme.Note that the reencrypted form of key blockSi,j (i.e., Si,j∗∗) is denoted as the two-tuples {μi,j,υi,j} and each of t CSPs will send it together with encrypted data block Ci,j to the user. Due to different identifications, different users would receive different form of Si,j∗∗.


## 4.5.2. Key Blocks Decryption

Upon user receiving allt encrypted key blocks (i.e., {μi,j,υi,j}) from t CSPs (here, we assume that user could identify the identifications of all t CSPs who send data), he/she could decrypt them with his/her secret key, r·H(uID), shown as follows:(13)Si,j∗=υi,j⊕Hle^HbBir·HuID,μi,j,where υi,j,μi,j are included in the encrypted form of Si,j, r is the secret value shared between owner and the user, Bi is the bill for Ci sent by the proxy, and Hl(·),Hb(·) are public parameters we prepared in ourSetup phase. Finally, user could decrypt Si,j∗ with L.(14)Si,j=Si,j∗⊕L.


## 4.5.3. File Decryption

For obtaining plaintext form of original data fileFi, after decrypting all t encrypted key blocks, the data user could obtain the original unencrypted encryption key Ki by decoding t unencrypted key blocks with dispersal matrix A. Then user decrypts each of encrypted data blocks in Ci and decode them in the same way. Now user could obtain the plaintext form of original data file Fi. The detailed processes of searching and downloading encrypted data/key blocks are summarized in Figure 2.Figure 2
The processes of search and download encrypted data/key blocks.


## 4.6. Correctness Analysis

In this section, we will show why data user could correctly decrypt the encrypted key blocks from each CSP if and only if the two bills of one corresponding data file (i.e., the bill from proxy and the bill form CSP) are exactly equal to each other. Without loss of generality, taking the key blockSi,j as an example, according to the encryption given by (12) and the decryption process shown in (13) and (14), we can prove that Si,j could be correctly decrypted when Bi=Bi′, as shown as follows.Firstly, the reencrypted form ofSi,j(Si,j∗∗) is shown as follows:(15)Si,j∗∗=μi,j,υi,j=gq,Si,j∗⊕Hle^HbBi′HuID,Pur=gq,Si,j⊕L⊕Hle^HbBi′HuID,Pur.Secondly, if and only ifBi=Bi′, we can correctly decrypt Si,j∗, as shown as follows:(16)υi,j⊕Hle^HbBir·HuID,μi,j=Si,j∗⊕Hlαi,jq⊕Hle^HbBir·HuID,μi=Si,j∗⊕Hle^HbBi′HuID,Puq⊕Hle^HbBir·HuID,gq=Si,j∗⊕Hle^HbBi′HuID,Puq⊕Hle^HbBiHuID,Puq=Si,j∗.Obviously, if we successfully decryptSi,j∗, we can correctly decrypt Si,j∗ as secret binary number L; we omit the correctness proof here.


## 4.7. Summary of Scheme

Now we summarize our proposed scheme in terms of reliability and flexibility. The detailed analyses about security and efficiency are shown in Section5.


### 4.7.1. Reliability

The(n,t) Reed-Solomon (RS) erasure-correcting code guarantees the reliability of our system. If there are some errors, such as data loss (key blocks or data blocks) occurring in some CSPs, the properties of erasure-correcting code could help the system to recover the complete data in time. In practice, when the owner deploys cloud services, some mature technology like virtual machines (VM) replication also could be used to enhance the data reliability, and the efficient issues like huge network resource consumption in failure recovery process have been deeply researched [21] to improve the quality of data service. That is to say, many technological means could guarantee the reliability of our system.


### 4.7.2. Flexibility

The owner outsources the (1) encrypted data blocks, (2) encrypted key blocks, and (3) encrypted index to the multicloud alliance and proxy, respectively. Therefore, data user could search what he/she needs in outsourced cloud data and download them as well as corresponding encrypted key blocks and finally decrypt the key and data. The whole data sharing process does not need the owner to remain online after finishing the upload process. It obviously brings significant flexibility to data owner.


## 4.7.1. Reliability

The(n,t) Reed-Solomon (RS) erasure-correcting code guarantees the reliability of our system. If there are some errors, such as data loss (key blocks or data blocks) occurring in some CSPs, the properties of erasure-correcting code could help the system to recover the complete data in time. In practice, when the owner deploys cloud services, some mature technology like virtual machines (VM) replication also could be used to enhance the data reliability, and the efficient issues like huge network resource consumption in failure recovery process have been deeply researched [21] to improve the quality of data service. That is to say, many technological means could guarantee the reliability of our system.


## 4.7.2. Flexibility

The owner outsources the (1) encrypted data blocks, (2) encrypted key blocks, and (3) encrypted index to the multicloud alliance and proxy, respectively. Therefore, data user could search what he/she needs in outsourced cloud data and download them as well as corresponding encrypted key blocks and finally decrypt the key and data. The whole data sharing process does not need the owner to remain online after finishing the upload process. It obviously brings significant flexibility to data owner.


## 5. Security and Performance Analysis

### 5.1. Security Analysis

We analyze the security of our system about the 3 aspects we mentioned in Section2.4.1: data confidentiality, index and query privacy, and confirmable bills.


#### 5.1.1. Data Confidentiality

The AES encryption algorithm is utilized to encrypt the outsourced data in our scheme. In general, we consider that the AES algorithm with random 128-bit key is secure; that is, the only way to destroy the data confidentiality is to deduce the 128-bit encryption (decryption) key. Except from completely guessing the key, there are two other kinds of attacks that adversary can carry out based on the threat model we defined in Section2.3. Assuming that the adversary wants to deduce one of the decryption keys Ki for the encrypted data block collection Ci, the specific attacks can be shown as follows:(i)
Attack-1: after receiving all encrypted data blocks and encrypted key blocks, there are more than t CSPs colluding together for deducing one of the encryption keys Ki; that is, the adversary can totally obtain more than t encrypted data/key blocks(ii)
Attack-2: when the t CSPs send t encrypted data blocks ({…,Ci,j,…}) and t reencrypted key blocks ({…,Si,j∗∗,…}) to one user, other users would like to eavesdrop the sending information to deduce Ki and further obtain the plaintext form of data file FiAs forAttack-1, the secret binary number L is used to protect each encrypted key block Si,j∗. According to the encryption process shown in (8), since the users in our system would not collude with any CSP, the adversary can only deduce the 128-bit L based on completely guessing way. Such difficulty is equal to guessing AES key; that is, our system is secure in this case.As forAttack-2, all users have the same secret value L which can successfully decrypt the encrypted key blocks (e.g., Si,j∗→Si,j), but the “curious" ones have to decrypt the reencrypted key blocks firstly (e.g., Si,j∗∗→Si,j∗). In our scheme, the secure identity-based encryption algorithm proposed by Boneh and Franklin [22] is used to protect the confidentiality of reencrypted key blocks (i.e., Si,j∗∗). Recalling the reencryption process we proposed in (12), the only difference compared with classical IBE algorithm in [22] is that we import the hash value of bill Bi into encryption, but it does not influence the security of encryption algorithm. The detailed security analysis of IBE is shown in literature [22], so we omit it here.The above two kinds of attacks are the two strongest attacks under the threat model we defined; that is, if our system can successfully resist the above two attacks, other weaker attacks also cannot work well. In summary, the data confidentiality can be protected well in our scheme.


#### 5.1.2. Index/Query Privacy

As for index privacy, since we only encrypt the keywords in the index, so if we can prove the security of index keywords encryption algorithm, we say that the index privacy is well protected. Recall the form of encrypted keywords in index:(17)w∗=gHL∥wmodp-1.Firstly, the discrete logarithm problem in Zp with large prime p prevents the proxy from knowing the hash value H(L∥w), even if the proxy could guess the encrypted keyword by trying all keywords in dictionary, but under the security assumption, in our threat model, users would not collude with proxy or any other adversary, which means that the proxy cannot obtain the secret value L. Therefore the proxy cannot deduce any plaintext information about encrypted keywords in index.As for query privacy, before we prove the security of query keywords encryption, we first define a traditional challenger-adversary game. The challenger firstly gives a public keypk to the adversary and then the adversary randomly chooses two query keywords w0 and w1 and sends them to the challenger. Upon receiving w0 and w1, the challenger randomly chooses ws (s=0 or s=1) with equal probability 1/2 and then sends ws∗=Enc(ws,pk) to the adversary. The adversary tries to guess the value of s and outputs its guess s′. The adversary’s advantage of this game is the probability Pr[s=s′]-1/2. Generally, the encryption algorithm is regarded as semantically secure against a chosen plaintext attack (CPA) if the adversary’s advantage is negligible.Theorem 1.
If DDH (Decisional Diffie-Hellman) problem is hard, our keywords encryption is semantically secure.Proof.
We assume that there is a polynomial time algorithmA that has a nonnegligible advantage ε as the adversary in the game described above. Then we define a DDH adversary B that could access A and achieves a nonnegligible advantage. B is given the tuple (g,gr,gH(L∥w),T) as input. Now, B tries to guess whether T is equal to gr·H(L∥w) or T is a random value; we denote γ=0 as T=gr·H(w) and γ=1 as T is random.
Firstly,B gives the tuple (g,gr) to A as input and then A randomly chooses keywords w0 and w1 and sends them to B.
Secondly,B sets a bit s randomly and sends ciphertext C1=gr,C2=gH(L∥ws)·T to A.
Thirdly,A sends B a bit s′, which is its guess for s. B guesses that γ=0 if and only if s′=s.Now we analyze the two situations ofγ:(i)
Ifγ=0 (i.e., T=gr·H(L∥ws)), then C2=gH(L∥ws)·T is a valid encryption for keywords encryption. In this case, A will guess correctly with probability 1/2+ε.(ii)
Ifγ=1 (i.e., T is random), the keywords encryption adversary A receives the value gH(L∥ws)·TH(L∥ws), where T is random value. In this case, s is hidden to A, so the probability that A will guess it is simply 1/2.Therefore, the probability thatB could successfully solve the DDH problem is shown as follows:(18)Pr=1212+ε+12·12=12+ε2.Since ε is nonnegligible, this demonstrates that B violates the assumption that DDH is hard.


#### 5.1.3. Confirmable Bills

The method that regards the exchange bill as a part of encryption key for reencrypting key blocks protects the bills from being forged. From the analysis we mentioned in Section4.6, we find that the user could not decrypt the reencryption key blocks successfully with a high probability under the threat model we defined in Section 2.3. Specifically, in our scheme, user randomly chooses t CSPs from the whole multicloud alliance for retrieving encryption key Ki. According to the security assumption we defined above, a small part of CSPs can be completely trusted; that is to say, if we choose proper parameters for n and t, it is highly possible that there is at least one trusted CSP in the randomly chosen t CSPs. As we say in Section 4.5.2, the user could identify the identifications of all t CSPs that send data, and user would not collude with proxy; therefore these t CSPs are randomly chosen by user; there does not exist the situation where proxy chooses t compromised CSPs that are not wholly chosen by user. Hence, even if the proxy colludes with some CSPs to forge bill Bi for Ci, there is at least one reencrypted key block that cannot be correctly decrypted by data user (see (16)), not to mention to obtain the correct unencrypted data file Fi. Of course, once the user fails to decrypt the data file, he/she will report an error to the system, which could help the owner detect whether the proxy or some CSPs forge the bills immediately.From the above analysis, the probability that all randomly chosen CSPs are semitrusted (i.e., adversary could successfully deceive the owner in terms of forging the one of the bills) can be calculated as follows:(19)Pr=Cn·1-PTtCnt,where PT denotes the proportion of trusted CSPs in whole multicloud alliance, n is the total number of CSPs in the whole multicloud alliance, and t is the encoding parameter that owner chooses. We assume that there are a total of 50 CSPs in the multicloud alliance and then analyze the successful probability for forging one bill based on different PT and parameter t as Figure 3 shows.Figure 3
The successful probability for forging one bill.From Figure3, we can see that larger t and PT will lead to lower probability that adversary can successfully deceive the owner for one forged bill. When t≥28 and PT≥16%, the probability that owner suffers such collusive attack is negligible. However, we have to say that even if the owner chooses proper t and the multicloud alliance is relatively secure (i.e., higher PT), there still exists the situation where the randomly chosen t CSPs are all semitrusted. In this case, all the key blocks would be correctly decrypted. In fact, there is a tradeoff between the high reliability and high security (the “security" here particularly means the correctness of exchange bills) of our data sharing scheme. On one hand, an extreme situation is to choose n=t as the encoding parameter; under our threat model that a small part of CSPs is wholly trusted, the attack above will never be carried out successfully. But if there are some errors like data losses in some CSPs, the system could not give the complete original data file to the user. On the other hand, if t is far less than n, the probability that proxy successfully colludes with the semitrusted CSPs will be high. In a word, the contradiction between reliability and security is still not fully solved in this paper. We will continue to research this problem in the future.


### 5.2. Performance Analysis

We implemented the proposed scheme using by C language in Windows 10 operation system and tested its efficiency in real-world data files: the Request for Comments (RFC) [23]. Since the upload process executed by owner can be regarded as the precomputation that will be executed only once, we only focus on the time cost of users and the communication cost of the proxy. Specifically, it includes (1) the time of trapdoor generation, (2) the time of search, (3) the time of key blocks reencryption, (4) the time of reencrypted key blocks decryption, and (5) the traffic analysis of proxy. Of course, the energy consumption is also an important indicator to evaluate the performance of such data-intensive cloud service [24], but due to the restricted experimental conditions, we would not discuss it in this paper. Our experiments are conducted on a system with an Intel(R) Core (TM) i5-3470 processor running at 3.74 GHz, 16.00 GB of RAM, and a 7200 RPM Western Digital 1 TB Serial ATA drive. All results represented the mean of 20 trials.


#### 5.2.1. Time of Trapdoor Generation

According to (9), the encryption algorithm for generating trapdoor for each query keyword totally includes two modular exponentiation operations; that is, the time complexity of trapdoor generation in our schemes is O(N2), where N denotes the size of dictionary. Figure 4 shows that the time of trapdoor generation increases linearly with N increasing.Figure 4
The time of trapdoor generation.


#### 5.2.2. Time of Search

The proxy should traverse the inverted indexI and rank the data files according to the number of query keywords in the file. Figure 6(a) shows that, with the same number of query keywords and data files, the search time increases almost linearly with the size of dictionary increasing. Figure 6(b) shows that, with the same number of data files and the same size of dictionary, the search time increases almost linearly with the number of query keywords increasing. But the search time cost is not significantly affected by the number of data files due to the structure of our inverted index; specifically, after locating query keywords, all candidates are filtered out for ranking, while the rank operation will not cost too much time, as shown in Figure 6(c).


#### 5.2.3. Time of Key Blocks Reencryption

Each of thet randomly chosen CSPs will reencrypt one encrypted key block for one data file as given in (12). Since the t CSPs reencrypt encrypted key blocks simultaneously, the waiting time for user is only related to the number of data files that will be downloaded by data user (top-k ranked results). That is, the time complexity of key blocks reencryption is O(k). As shown in Figure 5, with k increasing, the time of reencryption increases almost linearly.Figure 5
The time of key block reencryption.Figure 6
The time of search.
(a)
For different number of query keywords with the same size of dictionary,W = 4000, and for the same number of query data files, n = 2000 (b)
For different size of dictionary with the same number of query keywords,Q = 5, and for the same number of query data files, n = 2000 (c)
For different number of data files with the same size of dictionary,W = 4000, and for the same number of query keywords, Q = 5


#### 5.2.4. Time of Reencrypted Key Blocks Decryption

Upon receiving all reencrypted key blocks corresponding to retrievedk data files (i.e., encrypted data block collections), the user needs to decrypt them as given in (13). Obviously, the user totally decrypts t·k reencrypted key blocks. Figure 7 shows that, with the increasing of parameter t or k, the time of decryption increases almost linearly.Figure 7
The time of reencrypted key blocks decryption.
(a)
For different parametert with the same number of retrieved data files, k = 20 (b)
For different number of retrieved data files with the same parametert, t = 30


#### 5.2.5. Traffic Analysis of Proxy

Since proxy plays as “Interaction Center" in our system, it is necessary to analyze its traffic. The whole communication process of proxy can be divided into two phases. Specifically, the first one is “upload"; the proxy only receives the encrypted index from data owner; the second one is “download"; the proxy receives search request from data user, sends data request to multicloud alliance, and sends all corresponding bills to data user.According to the above two phases, the complexity of communication of proxy can be shown in Table2. We assume that the encrypted keyword is 128 bytes, the identification of encrypted data/key block or CSP is about 128 bytes, and the size of a bill is about 512 bytes. Then we set the number of documents m=5000, the number of CSPs in whole multicloud alliance (i.e., the encode parameter n) is 50, the encode parameter t=35, the size of dictionary W=12000, the number of keywords in query Q=5, and the search parameter k=50. Based on such parameter settings, we can obtain that the whole communication cost of proxy in upload phase is about 63 M, and in download phase it is about 0.45 M. Although the communication cost in upload is a little big, it is one-time process for uploading index. In a word, even the communication resource-constrained device could play as proxy.Table 2
The traffic analysis of proxy.
Data owner Data user Multicloud Upload O W + m + 2 m n 0 0 Download 0 O t + Q + k O 2 k t


## 5.1. Security Analysis

We analyze the security of our system about the 3 aspects we mentioned in Section2.4.1: data confidentiality, index and query privacy, and confirmable bills.


### 5.1.1. Data Confidentiality

The AES encryption algorithm is utilized to encrypt the outsourced data in our scheme. In general, we consider that the AES algorithm with random 128-bit key is secure; that is, the only way to destroy the data confidentiality is to deduce the 128-bit encryption (decryption) key. Except from completely guessing the key, there are two other kinds of attacks that adversary can carry out based on the threat model we defined in Section2.3. Assuming that the adversary wants to deduce one of the decryption keys Ki for the encrypted data block collection Ci, the specific attacks can be shown as follows:(i)
Attack-1: after receiving all encrypted data blocks and encrypted key blocks, there are more than t CSPs colluding together for deducing one of the encryption keys Ki; that is, the adversary can totally obtain more than t encrypted data/key blocks(ii)
Attack-2: when the t CSPs send t encrypted data blocks ({…,Ci,j,…}) and t reencrypted key blocks ({…,Si,j∗∗,…}) to one user, other users would like to eavesdrop the sending information to deduce Ki and further obtain the plaintext form of data file FiAs forAttack-1, the secret binary number L is used to protect each encrypted key block Si,j∗. According to the encryption process shown in (8), since the users in our system would not collude with any CSP, the adversary can only deduce the 128-bit L based on completely guessing way. Such difficulty is equal to guessing AES key; that is, our system is secure in this case.As forAttack-2, all users have the same secret value L which can successfully decrypt the encrypted key blocks (e.g., Si,j∗→Si,j), but the “curious" ones have to decrypt the reencrypted key blocks firstly (e.g., Si,j∗∗→Si,j∗). In our scheme, the secure identity-based encryption algorithm proposed by Boneh and Franklin [22] is used to protect the confidentiality of reencrypted key blocks (i.e., Si,j∗∗). Recalling the reencryption process we proposed in (12), the only difference compared with classical IBE algorithm in [22] is that we import the hash value of bill Bi into encryption, but it does not influence the security of encryption algorithm. The detailed security analysis of IBE is shown in literature [22], so we omit it here.The above two kinds of attacks are the two strongest attacks under the threat model we defined; that is, if our system can successfully resist the above two attacks, other weaker attacks also cannot work well. In summary, the data confidentiality can be protected well in our scheme.


### 5.1.2. Index/Query Privacy

As for index privacy, since we only encrypt the keywords in the index, so if we can prove the security of index keywords encryption algorithm, we say that the index privacy is well protected. Recall the form of encrypted keywords in index:(17)w∗=gHL∥wmodp-1.Firstly, the discrete logarithm problem in Zp with large prime p prevents the proxy from knowing the hash value H(L∥w), even if the proxy could guess the encrypted keyword by trying all keywords in dictionary, but under the security assumption, in our threat model, users would not collude with proxy or any other adversary, which means that the proxy cannot obtain the secret value L. Therefore the proxy cannot deduce any plaintext information about encrypted keywords in index.As for query privacy, before we prove the security of query keywords encryption, we first define a traditional challenger-adversary game. The challenger firstly gives a public keypk to the adversary and then the adversary randomly chooses two query keywords w0 and w1 and sends them to the challenger. Upon receiving w0 and w1, the challenger randomly chooses ws (s=0 or s=1) with equal probability 1/2 and then sends ws∗=Enc(ws,pk) to the adversary. The adversary tries to guess the value of s and outputs its guess s′. The adversary’s advantage of this game is the probability Pr[s=s′]-1/2. Generally, the encryption algorithm is regarded as semantically secure against a chosen plaintext attack (CPA) if the adversary’s advantage is negligible.Theorem 1.
If DDH (Decisional Diffie-Hellman) problem is hard, our keywords encryption is semantically secure.Proof.
We assume that there is a polynomial time algorithmA that has a nonnegligible advantage ε as the adversary in the game described above. Then we define a DDH adversary B that could access A and achieves a nonnegligible advantage. B is given the tuple (g,gr,gH(L∥w),T) as input. Now, B tries to guess whether T is equal to gr·H(L∥w) or T is a random value; we denote γ=0 as T=gr·H(w) and γ=1 as T is random.
Firstly,B gives the tuple (g,gr) to A as input and then A randomly chooses keywords w0 and w1 and sends them to B.
Secondly,B sets a bit s randomly and sends ciphertext C1=gr,C2=gH(L∥ws)·T to A.
Thirdly,A sends B a bit s′, which is its guess for s. B guesses that γ=0 if and only if s′=s.Now we analyze the two situations ofγ:(i)
Ifγ=0 (i.e., T=gr·H(L∥ws)), then C2=gH(L∥ws)·T is a valid encryption for keywords encryption. In this case, A will guess correctly with probability 1/2+ε.(ii)
Ifγ=1 (i.e., T is random), the keywords encryption adversary A receives the value gH(L∥ws)·TH(L∥ws), where T is random value. In this case, s is hidden to A, so the probability that A will guess it is simply 1/2.Therefore, the probability thatB could successfully solve the DDH problem is shown as follows:(18)Pr=1212+ε+12·12=12+ε2.Since ε is nonnegligible, this demonstrates that B violates the assumption that DDH is hard.


### 5.1.3. Confirmable Bills

The method that regards the exchange bill as a part of encryption key for reencrypting key blocks protects the bills from being forged. From the analysis we mentioned in Section4.6, we find that the user could not decrypt the reencryption key blocks successfully with a high probability under the threat model we defined in Section 2.3. Specifically, in our scheme, user randomly chooses t CSPs from the whole multicloud alliance for retrieving encryption key Ki. According to the security assumption we defined above, a small part of CSPs can be completely trusted; that is to say, if we choose proper parameters for n and t, it is highly possible that there is at least one trusted CSP in the randomly chosen t CSPs. As we say in Section 4.5.2, the user could identify the identifications of all t CSPs that send data, and user would not collude with proxy; therefore these t CSPs are randomly chosen by user; there does not exist the situation where proxy chooses t compromised CSPs that are not wholly chosen by user. Hence, even if the proxy colludes with some CSPs to forge bill Bi for Ci, there is at least one reencrypted key block that cannot be correctly decrypted by data user (see (16)), not to mention to obtain the correct unencrypted data file Fi. Of course, once the user fails to decrypt the data file, he/she will report an error to the system, which could help the owner detect whether the proxy or some CSPs forge the bills immediately.From the above analysis, the probability that all randomly chosen CSPs are semitrusted (i.e., adversary could successfully deceive the owner in terms of forging the one of the bills) can be calculated as follows:(19)Pr=Cn·1-PTtCnt,where PT denotes the proportion of trusted CSPs in whole multicloud alliance, n is the total number of CSPs in the whole multicloud alliance, and t is the encoding parameter that owner chooses. We assume that there are a total of 50 CSPs in the multicloud alliance and then analyze the successful probability for forging one bill based on different PT and parameter t as Figure 3 shows.Figure 3
The successful probability for forging one bill.From Figure3, we can see that larger t and PT will lead to lower probability that adversary can successfully deceive the owner for one forged bill. When t≥28 and PT≥16%, the probability that owner suffers such collusive attack is negligible. However, we have to say that even if the owner chooses proper t and the multicloud alliance is relatively secure (i.e., higher PT), there still exists the situation where the randomly chosen t CSPs are all semitrusted. In this case, all the key blocks would be correctly decrypted. In fact, there is a tradeoff between the high reliability and high security (the “security" here particularly means the correctness of exchange bills) of our data sharing scheme. On one hand, an extreme situation is to choose n=t as the encoding parameter; under our threat model that a small part of CSPs is wholly trusted, the attack above will never be carried out successfully. But if there are some errors like data losses in some CSPs, the system could not give the complete original data file to the user. On the other hand, if t is far less than n, the probability that proxy successfully colludes with the semitrusted CSPs will be high. In a word, the contradiction between reliability and security is still not fully solved in this paper. We will continue to research this problem in the future.


## 5.1.1. Data Confidentiality

The AES encryption algorithm is utilized to encrypt the outsourced data in our scheme. In general, we consider that the AES algorithm with random 128-bit key is secure; that is, the only way to destroy the data confidentiality is to deduce the 128-bit encryption (decryption) key. Except from completely guessing the key, there are two other kinds of attacks that adversary can carry out based on the threat model we defined in Section2.3. Assuming that the adversary wants to deduce one of the decryption keys Ki for the encrypted data block collection Ci, the specific attacks can be shown as follows:(i)
Attack-1: after receiving all encrypted data blocks and encrypted key blocks, there are more than t CSPs colluding together for deducing one of the encryption keys Ki; that is, the adversary can totally obtain more than t encrypted data/key blocks(ii)
Attack-2: when the t CSPs send t encrypted data blocks ({…,Ci,j,…}) and t reencrypted key blocks ({…,Si,j∗∗,…}) to one user, other users would like to eavesdrop the sending information to deduce Ki and further obtain the plaintext form of data file FiAs forAttack-1, the secret binary number L is used to protect each encrypted key block Si,j∗. According to the encryption process shown in (8), since the users in our system would not collude with any CSP, the adversary can only deduce the 128-bit L based on completely guessing way. Such difficulty is equal to guessing AES key; that is, our system is secure in this case.As forAttack-2, all users have the same secret value L which can successfully decrypt the encrypted key blocks (e.g., Si,j∗→Si,j), but the “curious" ones have to decrypt the reencrypted key blocks firstly (e.g., Si,j∗∗→Si,j∗). In our scheme, the secure identity-based encryption algorithm proposed by Boneh and Franklin [22] is used to protect the confidentiality of reencrypted key blocks (i.e., Si,j∗∗). Recalling the reencryption process we proposed in (12), the only difference compared with classical IBE algorithm in [22] is that we import the hash value of bill Bi into encryption, but it does not influence the security of encryption algorithm. The detailed security analysis of IBE is shown in literature [22], so we omit it here.The above two kinds of attacks are the two strongest attacks under the threat model we defined; that is, if our system can successfully resist the above two attacks, other weaker attacks also cannot work well. In summary, the data confidentiality can be protected well in our scheme.


## 5.1.2. Index/Query Privacy

As for index privacy, since we only encrypt the keywords in the index, so if we can prove the security of index keywords encryption algorithm, we say that the index privacy is well protected. Recall the form of encrypted keywords in index:(17)w∗=gHL∥wmodp-1.Firstly, the discrete logarithm problem in Zp with large prime p prevents the proxy from knowing the hash value H(L∥w), even if the proxy could guess the encrypted keyword by trying all keywords in dictionary, but under the security assumption, in our threat model, users would not collude with proxy or any other adversary, which means that the proxy cannot obtain the secret value L. Therefore the proxy cannot deduce any plaintext information about encrypted keywords in index.As for query privacy, before we prove the security of query keywords encryption, we first define a traditional challenger-adversary game. The challenger firstly gives a public keypk to the adversary and then the adversary randomly chooses two query keywords w0 and w1 and sends them to the challenger. Upon receiving w0 and w1, the challenger randomly chooses ws (s=0 or s=1) with equal probability 1/2 and then sends ws∗=Enc(ws,pk) to the adversary. The adversary tries to guess the value of s and outputs its guess s′. The adversary’s advantage of this game is the probability Pr[s=s′]-1/2. Generally, the encryption algorithm is regarded as semantically secure against a chosen plaintext attack (CPA) if the adversary’s advantage is negligible.Theorem 1.
If DDH (Decisional Diffie-Hellman) problem is hard, our keywords encryption is semantically secure.Proof.
We assume that there is a polynomial time algorithmA that has a nonnegligible advantage ε as the adversary in the game described above. Then we define a DDH adversary B that could access A and achieves a nonnegligible advantage. B is given the tuple (g,gr,gH(L∥w),T) as input. Now, B tries to guess whether T is equal to gr·H(L∥w) or T is a random value; we denote γ=0 as T=gr·H(w) and γ=1 as T is random.
Firstly,B gives the tuple (g,gr) to A as input and then A randomly chooses keywords w0 and w1 and sends them to B.
Secondly,B sets a bit s randomly and sends ciphertext C1=gr,C2=gH(L∥ws)·T to A.
Thirdly,A sends B a bit s′, which is its guess for s. B guesses that γ=0 if and only if s′=s.Now we analyze the two situations ofγ:(i)
Ifγ=0 (i.e., T=gr·H(L∥ws)), then C2=gH(L∥ws)·T is a valid encryption for keywords encryption. In this case, A will guess correctly with probability 1/2+ε.(ii)
Ifγ=1 (i.e., T is random), the keywords encryption adversary A receives the value gH(L∥ws)·TH(L∥ws), where T is random value. In this case, s is hidden to A, so the probability that A will guess it is simply 1/2.Therefore, the probability thatB could successfully solve the DDH problem is shown as follows:(18)Pr=1212+ε+12·12=12+ε2.Since ε is nonnegligible, this demonstrates that B violates the assumption that DDH is hard.


## 5.1.3. Confirmable Bills

The method that regards the exchange bill as a part of encryption key for reencrypting key blocks protects the bills from being forged. From the analysis we mentioned in Section4.6, we find that the user could not decrypt the reencryption key blocks successfully with a high probability under the threat model we defined in Section 2.3. Specifically, in our scheme, user randomly chooses t CSPs from the whole multicloud alliance for retrieving encryption key Ki. According to the security assumption we defined above, a small part of CSPs can be completely trusted; that is to say, if we choose proper parameters for n and t, it is highly possible that there is at least one trusted CSP in the randomly chosen t CSPs. As we say in Section 4.5.2, the user could identify the identifications of all t CSPs that send data, and user would not collude with proxy; therefore these t CSPs are randomly chosen by user; there does not exist the situation where proxy chooses t compromised CSPs that are not wholly chosen by user. Hence, even if the proxy colludes with some CSPs to forge bill Bi for Ci, there is at least one reencrypted key block that cannot be correctly decrypted by data user (see (16)), not to mention to obtain the correct unencrypted data file Fi. Of course, once the user fails to decrypt the data file, he/she will report an error to the system, which could help the owner detect whether the proxy or some CSPs forge the bills immediately.From the above analysis, the probability that all randomly chosen CSPs are semitrusted (i.e., adversary could successfully deceive the owner in terms of forging the one of the bills) can be calculated as follows:(19)Pr=Cn·1-PTtCnt,where PT denotes the proportion of trusted CSPs in whole multicloud alliance, n is the total number of CSPs in the whole multicloud alliance, and t is the encoding parameter that owner chooses. We assume that there are a total of 50 CSPs in the multicloud alliance and then analyze the successful probability for forging one bill based on different PT and parameter t as Figure 3 shows.Figure 3
The successful probability for forging one bill.From Figure3, we can see that larger t and PT will lead to lower probability that adversary can successfully deceive the owner for one forged bill. When t≥28 and PT≥16%, the probability that owner suffers such collusive attack is negligible. However, we have to say that even if the owner chooses proper t and the multicloud alliance is relatively secure (i.e., higher PT), there still exists the situation where the randomly chosen t CSPs are all semitrusted. In this case, all the key blocks would be correctly decrypted. In fact, there is a tradeoff between the high reliability and high security (the “security" here particularly means the correctness of exchange bills) of our data sharing scheme. On one hand, an extreme situation is to choose n=t as the encoding parameter; under our threat model that a small part of CSPs is wholly trusted, the attack above will never be carried out successfully. But if there are some errors like data losses in some CSPs, the system could not give the complete original data file to the user. On the other hand, if t is far less than n, the probability that proxy successfully colludes with the semitrusted CSPs will be high. In a word, the contradiction between reliability and security is still not fully solved in this paper. We will continue to research this problem in the future.


## 5.2. Performance Analysis

We implemented the proposed scheme using by C language in Windows 10 operation system and tested its efficiency in real-world data files: the Request for Comments (RFC) [23]. Since the upload process executed by owner can be regarded as the precomputation that will be executed only once, we only focus on the time cost of users and the communication cost of the proxy. Specifically, it includes (1) the time of trapdoor generation, (2) the time of search, (3) the time of key blocks reencryption, (4) the time of reencrypted key blocks decryption, and (5) the traffic analysis of proxy. Of course, the energy consumption is also an important indicator to evaluate the performance of such data-intensive cloud service [24], but due to the restricted experimental conditions, we would not discuss it in this paper. Our experiments are conducted on a system with an Intel(R) Core (TM) i5-3470 processor running at 3.74 GHz, 16.00 GB of RAM, and a 7200 RPM Western Digital 1 TB Serial ATA drive. All results represented the mean of 20 trials.


### 5.2.1. Time of Trapdoor Generation

According to (9), the encryption algorithm for generating trapdoor for each query keyword totally includes two modular exponentiation operations; that is, the time complexity of trapdoor generation in our schemes is O(N2), where N denotes the size of dictionary. Figure 4 shows that the time of trapdoor generation increases linearly with N increasing.Figure 4
The time of trapdoor generation.


### 5.2.2. Time of Search

The proxy should traverse the inverted indexI and rank the data files according to the number of query keywords in the file. Figure 6(a) shows that, with the same number of query keywords and data files, the search time increases almost linearly with the size of dictionary increasing. Figure 6(b) shows that, with the same number of data files and the same size of dictionary, the search time increases almost linearly with the number of query keywords increasing. But the search time cost is not significantly affected by the number of data files due to the structure of our inverted index; specifically, after locating query keywords, all candidates are filtered out for ranking, while the rank operation will not cost too much time, as shown in Figure 6(c).


### 5.2.3. Time of Key Blocks Reencryption

Each of thet randomly chosen CSPs will reencrypt one encrypted key block for one data file as given in (12). Since the t CSPs reencrypt encrypted key blocks simultaneously, the waiting time for user is only related to the number of data files that will be downloaded by data user (top-k ranked results). That is, the time complexity of key blocks reencryption is O(k). As shown in Figure 5, with k increasing, the time of reencryption increases almost linearly.Figure 5
The time of key block reencryption.Figure 6
The time of search.
(a)
For different number of query keywords with the same size of dictionary,W = 4000, and for the same number of query data files, n = 2000 (b)
For different size of dictionary with the same number of query keywords,Q = 5, and for the same number of query data files, n = 2000 (c)
For different number of data files with the same size of dictionary,W = 4000, and for the same number of query keywords, Q = 5


### 5.2.4. Time of Reencrypted Key Blocks Decryption

Upon receiving all reencrypted key blocks corresponding to retrievedk data files (i.e., encrypted data block collections), the user needs to decrypt them as given in (13). Obviously, the user totally decrypts t·k reencrypted key blocks. Figure 7 shows that, with the increasing of parameter t or k, the time of decryption increases almost linearly.Figure 7
The time of reencrypted key blocks decryption.
(a)
For different parametert with the same number of retrieved data files, k = 20 (b)
For different number of retrieved data files with the same parametert, t = 30


### 5.2.5. Traffic Analysis of Proxy

Since proxy plays as “Interaction Center" in our system, it is necessary to analyze its traffic. The whole communication process of proxy can be divided into two phases. Specifically, the first one is “upload"; the proxy only receives the encrypted index from data owner; the second one is “download"; the proxy receives search request from data user, sends data request to multicloud alliance, and sends all corresponding bills to data user.According to the above two phases, the complexity of communication of proxy can be shown in Table2. We assume that the encrypted keyword is 128 bytes, the identification of encrypted data/key block or CSP is about 128 bytes, and the size of a bill is about 512 bytes. Then we set the number of documents m=5000, the number of CSPs in whole multicloud alliance (i.e., the encode parameter n) is 50, the encode parameter t=35, the size of dictionary W=12000, the number of keywords in query Q=5, and the search parameter k=50. Based on such parameter settings, we can obtain that the whole communication cost of proxy in upload phase is about 63 M, and in download phase it is about 0.45 M. Although the communication cost in upload is a little big, it is one-time process for uploading index. In a word, even the communication resource-constrained device could play as proxy.Table 2
The traffic analysis of proxy.
Data owner Data user Multicloud Upload O W + m + 2 m n 0 0 Download 0 O t + Q + k O 2 k t


## 5.2.1. Time of Trapdoor Generation

According to (9), the encryption algorithm for generating trapdoor for each query keyword totally includes two modular exponentiation operations; that is, the time complexity of trapdoor generation in our schemes is O(N2), where N denotes the size of dictionary. Figure 4 shows that the time of trapdoor generation increases linearly with N increasing.Figure 4
The time of trapdoor generation.


## 5.2.2. Time of Search

The proxy should traverse the inverted indexI and rank the data files according to the number of query keywords in the file. Figure 6(a) shows that, with the same number of query keywords and data files, the search time increases almost linearly with the size of dictionary increasing. Figure 6(b) shows that, with the same number of data files and the same size of dictionary, the search time increases almost linearly with the number of query keywords increasing. But the search time cost is not significantly affected by the number of data files due to the structure of our inverted index; specifically, after locating query keywords, all candidates are filtered out for ranking, while the rank operation will not cost too much time, as shown in Figure 6(c).


## 5.2.3. Time of Key Blocks Reencryption

Each of thet randomly chosen CSPs will reencrypt one encrypted key block for one data file as given in (12). Since the t CSPs reencrypt encrypted key blocks simultaneously, the waiting time for user is only related to the number of data files that will be downloaded by data user (top-k ranked results). That is, the time complexity of key blocks reencryption is O(k). As shown in Figure 5, with k increasing, the time of reencryption increases almost linearly.Figure 5
The time of key block reencryption.Figure 6
The time of search.
(a)
For different number of query keywords with the same size of dictionary,W = 4000, and for the same number of query data files, n = 2000 (b)
For different size of dictionary with the same number of query keywords,Q = 5, and for the same number of query data files, n = 2000 (c)
For different number of data files with the same size of dictionary,W = 4000, and for the same number of query keywords, Q = 5


## 5.2.4. Time of Reencrypted Key Blocks Decryption

Upon receiving all reencrypted key blocks corresponding to retrievedk data files (i.e., encrypted data block collections), the user needs to decrypt them as given in (13). Obviously, the user totally decrypts t·k reencrypted key blocks. Figure 7 shows that, with the increasing of parameter t or k, the time of decryption increases almost linearly.Figure 7
The time of reencrypted key blocks decryption.
(a)
For different parametert with the same number of retrieved data files, k = 20 (b)
For different number of retrieved data files with the same parametert, t = 30


## 5.2.5. Traffic Analysis of Proxy

Since proxy plays as “Interaction Center" in our system, it is necessary to analyze its traffic. The whole communication process of proxy can be divided into two phases. Specifically, the first one is “upload"; the proxy only receives the encrypted index from data owner; the second one is “download"; the proxy receives search request from data user, sends data request to multicloud alliance, and sends all corresponding bills to data user.According to the above two phases, the complexity of communication of proxy can be shown in Table2. We assume that the encrypted keyword is 128 bytes, the identification of encrypted data/key block or CSP is about 128 bytes, and the size of a bill is about 512 bytes. Then we set the number of documents m=5000, the number of CSPs in whole multicloud alliance (i.e., the encode parameter n) is 50, the encode parameter t=35, the size of dictionary W=12000, the number of keywords in query Q=5, and the search parameter k=50. Based on such parameter settings, we can obtain that the whole communication cost of proxy in upload phase is about 63 M, and in download phase it is about 0.45 M. Although the communication cost in upload is a little big, it is one-time process for uploading index. In a word, even the communication resource-constrained device could play as proxy.Table 2
The traffic analysis of proxy.
Data owner Data user Multicloud Upload O W + m + 2 m n 0 0 Download 0 O t + Q + k O 2 k t


## 6. Related Work

### 6.1. Secure Data Sharing with IBE and PRE

The concept of identity-based encryption (IBE) was first introduced by Shamir [25]; then Boneh and Franklin  [22] proposed the first secure and practical IBE scheme with the computable bilinear map. Then Canetti et al. [26] designed the first construction for IBE which was provably secure without the random oracle model. Moving a step forward, in 2004, Boneh and Boyen [27] proposed two efficiency improved IBE schemes under the “selective-ID" model proposed in [26]. The IBE approach provides an efficient cryptographic system where the public key can be any arbitrary string and the secret key is extracted from a trusted party called a private key generator (PKG). Motivated by its significant advantage that owner could release from heavy load of managing certificates, Kackeri [9] utilized IBE in the secure data distribution system that only users with authorized identifications could access the encrypted data.Another popular secure data sharing method is proxy-based reencryption (PRE), which was first proposed by Blaze et al. [28]. With a proxy server, the PRE primitive can transfer a ciphertext designated for one user to another ciphertext designated for another user without knowing the plaintext content of data. After that, many PRE schemes have been proposed for the improved security or efficiency [29–31]. In 2006, Ateniese et al. [32] then improved the concept of PRE and employed it for remote data storage. In their scheme, owner encrypts his/her files and outsources them to proxy. The proxy can transfer the owner’s ciphertext to the ciphertext of the requester if and only if he/she has obtained a reencryption key from the owner. Then, combining technologies of IBE and PRE, Green and Ateniese [33] introduced the concept of identity-based proxy reencryption (IBPRE) scheme and then the IBPRE scheme is further developed in terms of security and functionality enhancement [34, 35]. The proxy in IBPRE schemes also plays a similar role to traditional PRE, but the transfer key is related to the identities of owners and users.However, when we utilize the method of IBE or PRE for data sharing system, it is necessary for data owner to remain online all the time (such as generating reencryption key for user in PRE schemes) or know the specific information about the data user (such as encrypting data according to the user’s identification in IBE schemes).


### 6.2. Secure Data Sharing with ABE

To address the mentioned problems of IBE and PRE, Goyal et al. [36] firstly proposed Key-Policy Attribute-Based Encryption, where the ciphertexts are labeled with sets of attributes and private keys are associated with access structures that control which ciphertexts a user is able to decrypt. Then, a number of works used ABE to realize fine-grained access control for outsourced data [12, 13, 37]. There is no doubt that the ABE schemes improve the scalability of data sharing system, so that the data owner could encrypt outsourced data for multiple users with one encryption key. Besides, ABE schemes also provide great flexibilities since only attributes of the user set instead of specific identity (or public key) need to be known by owner. But there are still some limits for directly using ABE scheme in our “Paid Data Sharing" model: one is that may be the owner even does not know the user’s attributes for one data file; another is that the authority in ABE system suffers from the key escrow problem [12, 16], since the authority can access all the encrypted files.Besides, Hiremath and Annapurna [38] discussed the framework and security issues at collaboration in multicloud computing environments; inspired by the “proxy as service" model they proposed, we design a distributed data/key storage system architecture in this paper.


## 6.1. Secure Data Sharing with IBE and PRE

The concept of identity-based encryption (IBE) was first introduced by Shamir [25]; then Boneh and Franklin  [22] proposed the first secure and practical IBE scheme with the computable bilinear map. Then Canetti et al. [26] designed the first construction for IBE which was provably secure without the random oracle model. Moving a step forward, in 2004, Boneh and Boyen [27] proposed two efficiency improved IBE schemes under the “selective-ID" model proposed in [26]. The IBE approach provides an efficient cryptographic system where the public key can be any arbitrary string and the secret key is extracted from a trusted party called a private key generator (PKG). Motivated by its significant advantage that owner could release from heavy load of managing certificates, Kackeri [9] utilized IBE in the secure data distribution system that only users with authorized identifications could access the encrypted data.Another popular secure data sharing method is proxy-based reencryption (PRE), which was first proposed by Blaze et al. [28]. With a proxy server, the PRE primitive can transfer a ciphertext designated for one user to another ciphertext designated for another user without knowing the plaintext content of data. After that, many PRE schemes have been proposed for the improved security or efficiency [29–31]. In 2006, Ateniese et al. [32] then improved the concept of PRE and employed it for remote data storage. In their scheme, owner encrypts his/her files and outsources them to proxy. The proxy can transfer the owner’s ciphertext to the ciphertext of the requester if and only if he/she has obtained a reencryption key from the owner. Then, combining technologies of IBE and PRE, Green and Ateniese [33] introduced the concept of identity-based proxy reencryption (IBPRE) scheme and then the IBPRE scheme is further developed in terms of security and functionality enhancement [34, 35]. The proxy in IBPRE schemes also plays a similar role to traditional PRE, but the transfer key is related to the identities of owners and users.However, when we utilize the method of IBE or PRE for data sharing system, it is necessary for data owner to remain online all the time (such as generating reencryption key for user in PRE schemes) or know the specific information about the data user (such as encrypting data according to the user’s identification in IBE schemes).


## 6.2. Secure Data Sharing with ABE

To address the mentioned problems of IBE and PRE, Goyal et al. [36] firstly proposed Key-Policy Attribute-Based Encryption, where the ciphertexts are labeled with sets of attributes and private keys are associated with access structures that control which ciphertexts a user is able to decrypt. Then, a number of works used ABE to realize fine-grained access control for outsourced data [12, 13, 37]. There is no doubt that the ABE schemes improve the scalability of data sharing system, so that the data owner could encrypt outsourced data for multiple users with one encryption key. Besides, ABE schemes also provide great flexibilities since only attributes of the user set instead of specific identity (or public key) need to be known by owner. But there are still some limits for directly using ABE scheme in our “Paid Data Sharing" model: one is that may be the owner even does not know the user’s attributes for one data file; another is that the authority in ABE system suffers from the key escrow problem [12, 16], since the authority can access all the encrypted files.Besides, Hiremath and Annapurna [38] discussed the framework and security issues at collaboration in multicloud computing environments; inspired by the “proxy as service" model they proposed, we design a distributed data/key storage system architecture in this paper.


## 7. Conclusion

In this paper, for the first time, we explore the problems in a practical secure data sharing scenario. Specifically, the data owner does not know which data users (even their attributes) will download and decrypt which outsourced data files of him/her, while the owner cannot always remain online and there is no trusted third party in the system. We utilize the secret sharing approach to split and encrypt the decryption key and then outsource it to multiple cloud service providers (CSPs). Such distributed key management not only protects the data confidentiality but also guarantees that if there are not enough CSPs collude with each other, the adversaries cannot successfully forge the bills for data transaction. In order to improve the reliability of such data service, we exploit the erasure-correcting code for distributing file to multiple CSPs. Even if there are data losses occurring in some CSPs, the data redundancies that erasure-correcting code produced can help to recover the complete outsourced data immediately. A semitrusted proxy that offered a secure and efficient keyword-based query function enables the data user to search what he/she needs in outsourced data files before downloading. Experiments on real-world dataset demonstrate the time efficiency of our proposed scheme.



---

*Source: 5634561-2018-04-30.xml*