# Co-Check: Collaborative Outsourced Data Auditing in Multicloud Environment

Authors: Jian Mao; Wenqian Tian; Yan Zhang; Jian Cui; Hanjun Ma; Jingdong Bian; Jianwei Liu; Jianhong Zhang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

With the increasing demand for ubiquitous connectivity, wireless technology has significantly improved our daily lives. Meanwhile, together with cloud-computing technology (e.g., cloud storage services and big data processing), new wireless networking technology becomes the foundation infrastructure of emerging communication networks. Particularly, cloud storage has been widely used in services, such as data outsourcing and resource sharing, among the heterogeneous wireless environments because of its convenience, low cost, and flexibility. However, users/clients lose the physical control of their data after outsourcing. Consequently, ensuring the integrity of the outsourced data becomes an important security requirement of cloud storage applications. In this paper, we present Co-Check, a collaborative multicloud data integrity audition scheme, which is based on BLS (Boneh-Lynn-Shacham) signature and homomorphic tags. According to the proposed scheme, clients can audit their outsourced data in a one-round challenge-response interaction with low performance overhead. Our scheme also supports dynamic data maintenance. The theoretical analysis and experiment results illustrate that our scheme is provably secure and efficient.


---

## Body

## 1. Introduction

With the increasing demand for ubiquitous connectivity, wireless technology has significantly improved our daily lives. Meanwhile, together with cloud-computing technology (e.g., cloud storage services and big data processing), heterogeneous wireless networking technology has become a foundation infrastructure widely adopted by emerging communication networks, for instance, IoT (Internet of Things), C-RAN (cloud radio access network), and body-area network, as shown in Figure1. Particularly, the cloud storage technique has been widely used in services, such as wireless data outsourcing and resource sharing, thanks to its convenience, low cost, and flexibility. Nowadays, online service providers, such as Amazon and Baidu, operate large data centers and offer unlimited storage capacity for users, relieving their burden of local data management and maintenance [1, 2]. In addition, cloud storage enables universal data access in any place. However, users lose the physical control of their outsourced data, while the cloud storage service provider is not always trustworthy. Dishonest service providers may conceal the fact that users’ data have been damaged due to some misoperations or unexpected accidents. Even worse, malicious service providers also may delete the data seldom accessed by users to gain more benefits. How to ensure the integrity of their remotely outsourced data becomes a serious concern for users selecting cloud storing services.Figure 1
Overall architecture of the multicloud based heterogeneous wireless network.Traditional data integrity verification solutions [3, 4], which are based on hash functions and digital signatures, are impractical to audit cloud data remotely due to their unacceptable communication and computational overhead to retrieve the outsourced files. To check the remote data integrity effectively without retrieving the whole outsourced document, Ateniense et al. presented the first probabilistic verification model calledprovable data possession (PDP) based on homomorphic cryptography algorithm andsampling techniques [5]. Taking the public verifiability into account, Ateniense et al. improved their approach [6]; Wang et al. also proposed a publicly verifiable cloud data audition scheme that supports dynamic data maintenance by using Merkle Hash Tree data structure [7]. Juels et al. introduced error correcting coding techniques and proposedProof of Retrievability (POR) mechanisms to audit cloud data and ensure data correction if data corruption happened.Most of these previous works mainly target the problem of data integrity audition in a single-cloud storage environment rather than a heterogeneous cloud infrastructure that collaborates multiple internal (private) and/or external (public) cloud resources [8, 9]. In the multicloud environment, users split their data, duplicate file blocks, and outsource them to different CSP (Cloud Service Provider) servers. The solutions above cannot enforce the data integrity checking efficiently in such an environment where data spread over multiple servers. Aiming at this problem, Zhu et al. propose a cooperative provable data possession (CPDP) scheme [8, 10] in the multicloud environment. However, in the CPDP scheme, the security parameter π′ is independent of other parameters; and thus servers can bypass the authentication by forging the parameter π′ in the response sequence. Moreover, in the process of third-party public verification, the third party needs to know where every data block is exactly stored. It poses a threat to users’ data storage privacy and increases the operation overhead for the third auditing party to maintain the storing state of file blocks. Moreover, besides the effectiveness, efficiency is also a significant concern for a data integrity auditing solution in the multicloud storage environment.In this paper, we presentCo-Check, a collaborative multicloud data integrity audition scheme, which is based on BLS signature and homomorphic tags. According to proposed scheme, users can audit their outsourced data in one challenge-response interaction with low communication cost. Our scheme also enables public verification and supports dynamic data maintenance that users can modify and delete the data with low performance overhead. The contributions made by this paper are summarized as follows.(i)
We propose an effective collaborative multicloud data audition scheme enabling users to conduct data integrity checking among multiple CPS server simultaneously in one-round challenge-response procedure.(ii)
The audition procedure of our scheme is stateless and supports unlimited challenge-response interactions. Moreover, the proposed scheme supports dynamic data maintenance efficiently.(iii)
We prototype our scheme and conduct system evaluation. The theoretical analysis and experiment results illustrate that our scheme is provably secure and efficient.Paper Organization. The rest of this paper is organized as follows. Section 2 describes the security goals, system model, and the overall architecture of our approach; Section 3 presents the collaborative multicloud data integrity audition scheme; in Section 4, we make the theoretical analysis and evaluate our protocol on security and performance aspects; Section 5 discusses the related work; and Section 6 concludes the paper.


## 2. Approach Overview

### 2.1. System Framework

As shown in Figure2, the general multicloud storage system includes three types of network entities.Figure 2
Multicloud based data storing for wireless communication systems.(i) Client (or User). (We use the termuser andclient exchangeably in this paper.) Clients outsource data to reduce local storage overhead and make use of the computation resources provided by the cloud service providers in multicloud storage system.(ii) Cloud Service Provider (CSP). CSPs that possess a large quantity of hardware and software resources are clustered to provide remote data storing services. We assume that there is an organizer in the CSP cluster, a mediation node that interacts with users and other CSPs.(iii) Third-Party Authority (TPA). TPA is an optional entity being partially trusted in the multicloud scenario.In the multicloud storage system shown in Figure2, the user splits her/his documents into several file blocks. The file blocks will distribute the cloud storage servers deployed by different cloud service providers. In addition, to promote the access efficiency and ensure the data retrievability, users might also duplicate the file blocks and spread the copies to several cloud servers.


### 2.2. Challenges and Goals

As the CSPs in the multicloud system cannot always be trustworthy, it is necessary for users to establish the integrity audition mechanism that ensures their outsourced data are stored correctly without unauthorized access by CSP servers or other entities. To make the audition more efficient, another challenge of data integrity audition in the multicloud environment is to conduct parallel checking, which means verifying the integrity of block files stored in different CSP servers simultaneously. Moreover, supporting securely dynamic maintenance is also a major concern of the multicloud data audition.Aiming to address the above challenges, the goal of this paper is to propose an effective multicloud data integrity audition mechanism satisfying the following requirements.(i)
Correctness: benign servers will prove themselves successfully and none of the misbehaved servers can bypass the checking.(ii)
Batch verification: the client can simultaneously verify the integrity of the file blocks distributed in different CSP servers without retrieving the file.(iii)
Stateless and unbounded checking: the audition procedure is stateless and supports unlimited challenge-response interactions.


### 2.3. Collaborative Data Integrity Audition Model

Our collaborative data audition model consists of three stages as we defined in our preliminary version [11]:initialization,challenge-response, andintegrity checking. Motivated by the sampling technique introduced by Ateniese et al. [5], users split their files and distribute the file blocks among the cloud service providers (CSPs) ininitialization and preprocessing stage. Meanwhile, users keep the corresponding metadata for the future audition. Here we use BLS signature to create thehomomorphic tags due to its homomorphic property. Instead of retrieving the whole file to verify its correctness, in stages II and III, users generate the challenges for audition by using parts of the metadata restored at the client side to prompt the audition efficiency and ensure that malicious CSPs cannot bypass the check with a high confidence rate. Additionally, our scheme also designates a subprocedure to support dynamic maintenance. The procedure of our scheme is shown in Figure 3.Figure 3
Collaborative data integrity audition procedure.(
1) Stage I: Initialization and Preprocessing. Stage I consists of steps (1)-(2) in Figure 3. In step (1), the user selects system parameters and generates keys for BLS algorithm used in the successive steps. Meanwhile, the user splits the file F into file block set and each file block mij consists of several file sectors. Then the user computes the homomorphic tags σij corresponding to the file sectors. After preprocessing the outsourced file, the user distributes the file blocks with the metadata for audition into the cloud servers belonging to the different CSPs and keeps the secret parameter locally.(
2) Stage II: Challenge-Response. Stage II includes steps (3)–(6) in Figure 3. When the user wants to audit her/his outsourced file, she/he computes a challenge sequence corresponding to the file blocks under test. The user sendsorganizer to the challenge sequence andorganizer will forward the challenges to the aimed CSP servers that contain the user’s file blocks. CSP servers calculate and return their proofs toorganizer.Organizer aggregates the proof received and sends the corresponding answer to the user.(
3) Stage III: Integrity Checking. Based on the received response fromorganizer, the user verifies the data integrity in step (7) shown in Figure 3. If data are stored correctly, the algorithm outputs “TRUE”; otherwise, it outputs “FALSE,” which means that there exist misbehaved CSP servers.Dynamic Maintenance. When users need to conduct dynamic operations on their outsourced data, they recreate tags corresponding to the new file sectors and send them to the organizer for updating.All the symbols used in this paper are listed in Notation.


## 2.1. System Framework

As shown in Figure2, the general multicloud storage system includes three types of network entities.Figure 2
Multicloud based data storing for wireless communication systems.(i) Client (or User). (We use the termuser andclient exchangeably in this paper.) Clients outsource data to reduce local storage overhead and make use of the computation resources provided by the cloud service providers in multicloud storage system.(ii) Cloud Service Provider (CSP). CSPs that possess a large quantity of hardware and software resources are clustered to provide remote data storing services. We assume that there is an organizer in the CSP cluster, a mediation node that interacts with users and other CSPs.(iii) Third-Party Authority (TPA). TPA is an optional entity being partially trusted in the multicloud scenario.In the multicloud storage system shown in Figure2, the user splits her/his documents into several file blocks. The file blocks will distribute the cloud storage servers deployed by different cloud service providers. In addition, to promote the access efficiency and ensure the data retrievability, users might also duplicate the file blocks and spread the copies to several cloud servers.


## 2.2. Challenges and Goals

As the CSPs in the multicloud system cannot always be trustworthy, it is necessary for users to establish the integrity audition mechanism that ensures their outsourced data are stored correctly without unauthorized access by CSP servers or other entities. To make the audition more efficient, another challenge of data integrity audition in the multicloud environment is to conduct parallel checking, which means verifying the integrity of block files stored in different CSP servers simultaneously. Moreover, supporting securely dynamic maintenance is also a major concern of the multicloud data audition.Aiming to address the above challenges, the goal of this paper is to propose an effective multicloud data integrity audition mechanism satisfying the following requirements.(i)
Correctness: benign servers will prove themselves successfully and none of the misbehaved servers can bypass the checking.(ii)
Batch verification: the client can simultaneously verify the integrity of the file blocks distributed in different CSP servers without retrieving the file.(iii)
Stateless and unbounded checking: the audition procedure is stateless and supports unlimited challenge-response interactions.


## 2.3. Collaborative Data Integrity Audition Model

Our collaborative data audition model consists of three stages as we defined in our preliminary version [11]:initialization,challenge-response, andintegrity checking. Motivated by the sampling technique introduced by Ateniese et al. [5], users split their files and distribute the file blocks among the cloud service providers (CSPs) ininitialization and preprocessing stage. Meanwhile, users keep the corresponding metadata for the future audition. Here we use BLS signature to create thehomomorphic tags due to its homomorphic property. Instead of retrieving the whole file to verify its correctness, in stages II and III, users generate the challenges for audition by using parts of the metadata restored at the client side to prompt the audition efficiency and ensure that malicious CSPs cannot bypass the check with a high confidence rate. Additionally, our scheme also designates a subprocedure to support dynamic maintenance. The procedure of our scheme is shown in Figure 3.Figure 3
Collaborative data integrity audition procedure.(
1) Stage I: Initialization and Preprocessing. Stage I consists of steps (1)-(2) in Figure 3. In step (1), the user selects system parameters and generates keys for BLS algorithm used in the successive steps. Meanwhile, the user splits the file F into file block set and each file block mij consists of several file sectors. Then the user computes the homomorphic tags σij corresponding to the file sectors. After preprocessing the outsourced file, the user distributes the file blocks with the metadata for audition into the cloud servers belonging to the different CSPs and keeps the secret parameter locally.(
2) Stage II: Challenge-Response. Stage II includes steps (3)–(6) in Figure 3. When the user wants to audit her/his outsourced file, she/he computes a challenge sequence corresponding to the file blocks under test. The user sendsorganizer to the challenge sequence andorganizer will forward the challenges to the aimed CSP servers that contain the user’s file blocks. CSP servers calculate and return their proofs toorganizer.Organizer aggregates the proof received and sends the corresponding answer to the user.(
3) Stage III: Integrity Checking. Based on the received response fromorganizer, the user verifies the data integrity in step (7) shown in Figure 3. If data are stored correctly, the algorithm outputs “TRUE”; otherwise, it outputs “FALSE,” which means that there exist misbehaved CSP servers.Dynamic Maintenance. When users need to conduct dynamic operations on their outsourced data, they recreate tags corresponding to the new file sectors and send them to the organizer for updating.All the symbols used in this paper are listed in Notation.


## 3. Collaborative Multicloud Data Integrity Audition Scheme

In this section, we present our collaborative multicloud data integrity audition scheme in detail. The notations and concepts employed in our work are illustrated below.(i)
π=p,G,GT,e,g is the system parameter. p is a big prime number and is the order of the cyclic group G; e:G×G→GT is a nondegenerate bilinear map. g is the generator of G.(ii)
l is the number of the CSPs, and the CSP set is represented as CSP1,CSP2,…,CSPl.(iii)
F is user’s file and Fn is the file name. The file F is separated into n blocks, each of which contains s sectors, F=mijn×s, where mij∈Zp.(iv)
Q is the challenge generated by users.(v)
H:0,1∗→G is a hash function.As shown in Figure3, our scheme includes three entities, auser, CSP servers, and anorganizer, which is also one of the CSP servers. The integrity checking scheme is fulfilled by the following eight steps.Step 1 (user setup).
(1)
KeyGen:KeyGen1λ→sk,pk.
The user selects secure parameterλ and system parameters π and H. She/he randomly selects an α∈Zp∗ as the private key. The public key is v←gα∈G. Then the user gets pk=v,g,sk=α.
(2)
File preprocessing:F→mijn×s.
The user splits the fileF into n blocks, each of which contains s parts. The file F is represented as follows: (1)F=m1m2⋮mn=m11m12⋯m1sm21m22⋯m2s⋮⋮⋯⋮mn1mn2⋯mns,mij∈Zp.
We assume thatnumii=1,…,n is the total number of copies corresponding to each data block mii=1,…,n stored in different CSPs, and Vii=1,…,n represents how many times each data is updated. The initial value of Vii=1,…,n is 0 for all the elements. We use χi=i∥numi∥Vii=1,…,n to represent it. ∥ represents concatenation.
(3)
TagGen:TagGensk,pk,F→σ.
The user randomly selectss parameters u1,…,us∈G and computes the tags σik←(H(Fn∥i∥k∥Vi)·∏j=1sujmij))α for k=1,…,numi corresponding to each data block mii=1,…,n and thus the set of all tags is obtained. As shown in Figure 4, mii=1,…,n represents data blocks from the file; each block is separated into s parts and every part of a block is represented as miji=1,…,n;j=1,…,s; σiki=1,…,n;k=1,…,numi represent numi tags corresponding to mi.Figure 4
Tag generating.Step 2 (data outsourcing).
The user sends the fileF and corresponding tags to the organizer, and the organizer distributes data blocks with corresponding tags to different CSP servers (as shown in Figure 5). If a file block is stored with several copies, every copy of the file block has a tag. For instance, data block mii=1,…,n is stored with numi copies, then there are numi tags, which means the CSPs should store data mi along with the tag σikk∈1,…,numi from the numi labels. The user computes the public parameter ψ=u,χ (u=u1,…,us,χ=χ1,…,χn) and sends it to the trusted third party for storage. The user keeps the private key at the client side.Figure 5
Data outsourcing.Step 3 (challenge creation, challenge (chal)).
When the user wants to audit the outsourced data, he or she computes a challenge,chal=Q=ij,aj∣ij∈1,…,n,aj∈Zp∗,j=1,…,c, and sends it to the organizer.Step 4 (challenge delivery, forward (chal)).
The organizer forwards the received challengechal=Q to the CSP servers, CSPk∈1,…,l. Without losing generality, we assume there are t CSP servers that store the blocks challenged by the user.Step 5 (proof creation and delivery,GenProofpk,Q,mi,σix→Pk).
∀
k
∈
1
,
…
,
l, the service provider CSPk computes the evidence according to the following formula:(2)p1kj=∑mi∈CSPkaimijmodpj=1,…,sp2k⟵∏mi∈CSPkσixai∈G.CSPk returns the proofs shown in (3) to the organizer:(3)Pk=p1k,p2kp1k=p1k1,p1k2,…,p1ks.Step 6 (proof aggregation and response,Aggregationpk,Q,P1,P2,…,Pt→P).
The organizer computesP1j=∑k=1tP1kjmodpj=1,2,…,s,P2←∏k=1tP2k∈G. The organizer returns the aggregated proof P, P=P1,P2, to the user, where P1=P11,P12,…,P1s.Step 7 (user verification).
After the user received the dataP=P1,P2 sent by the organizer, she/he gets the parameter ψ=u,χ from the trusted third party and verifies the response according to the formula (4)eP2,g=e∏i,ai∈Q∏k=1numiHFn∥i∥k∥Viai∏j=1sujp1j,v.If formula (4) holds, it means the outsourced data are stored correctly and the output is “TRUE”; otherwise, the output is “FALSE.”
We summarize the interactions of collaborative auditing in Figure6.
Dynamic Update. When users need to update data mi→m′, they should make a modification Vi=Vi+1 from χi=i∥numi∥Vi, compute the new label new_σik←(H(Fn∥i∥k∥Vi)·∏j=1sujmj′))α, k=1,…,numi, and send the updated χi along with the corresponding label σikk=1,…,numi to the organizer. After that, the organizer conducts the distributed storing operation. Due to the relevance between the label and the sequence of the data, the scheme could only realize part of the update operations, namely, data modification and deletion.Figure 6
Collaborative multicloud data integrity audition scheme.


## 4. Evaluation

### 4.1. Security Analysis

In this section, we prove two properties to ensure data integrity under our scheme.Theorem 1.
Correctness. If all CSP servers keep user’s data correctly, they can successfully pass the challenge-response verification procedure initiated by the user.Proof.
To verify the data correctness, according to step(7), the use computes eP2,g. It can be noticed in step (5)-(6) that P1j=∑k=1tP1kjmodpj=1,2,…,s and P2=∏k=1tP2k, where p1kj=∑mi∈CSPkaimijmodpj=1,…,s and p2k=∏mi∈CSPkσixai∈G.
According to the bilinear property of the Weil-paring function, we get(5)eP2,g=e∏k=1tP2k,g=e∏k=1t∏mi∈CSPkσixai,g=e∏k=1t∏mi∈CSPkHFn∥i∥k∥Vi·∏j=1sujmijaiα,g=e∏k=1t∏mi∈CSPkHFn∥i∥k∥Vi·∏j=1sujmijai,gα=e∏i,ai∈Q∏k=1numiHFn∥i∥k∥Viai∏j=1suj∑k=1t∑mi∈CSPkaimij,v=e∏i,ai∈Q∏k=1numiHFn∥i∥k∥Viai∏j=1sujp1j,v.
This completes our proof.Theorem 2.
If there exists a probabilistic polynomial time adversary adv and it is able to successfully convince the TPA to accept the fake proof information for a corrupted file in nonnegligible probability, then it is possible to construct a polynomial algorithmB to solve the computational Diffie-Hellman (CDH) problem by invoking adv with nonnegligible probability.Proof.
Suppose that the algorithmB is given an instance of the CDH problem tuple shown as follows:(6)g,ga,gb and its goal is to compute gab. The algorithm B will execute an interactive game with adv in the following game of security model.
Setup. Let v=ga be the public key of the user, and choose a hash function H:0,1∗→G which acts as random oracle in the following security proof. And for i=1 to s, it randomly selects ri to set ui=gri. Finally, it returns the public parameter params=p,G,g,u1,…,us,H to the adversary adv.
Hash Query. At any time, the adversary adv is able to adaptively query hash oracle for the string Fn∥i∥k∥Vi it submits. And to respond to these queries, the algorithm maintains an H-list which is initially empty and responds as follows: (1)
IfFn∥i∗∥k∥Vi,∗,∗ exists in the H-list, B retrieves the tuple Fn∥i∗∥k∥Vi,di,hi and sends hi the adversary adv.(2)
Otherwise,B chooses a bit di∈0,1 according to a bivariate distribution function Pr⁡di=0=τ and Pr⁡di=1=1-τ, where τ is a fixed probability value which will be determined later. Then B answers as follows:
(a)
Ifdi=0, B chooses a random number ti to compute hi=gti and return hi to the adversary. Then B inserts the tuple Fn∥i∗∥k∥Vi,di,hi to the H-list.(b)
Ifdi=1, B chooses a random number ti to compute hi=gbti and return hi to the adversary. Then B inserts the tuple Fn∥i∗∥k∥Vi,di,hi to the H-list.
TagGen Oracle. At any time, the adversary can adaptively query the TagGen oracle with message m. To respond to it, B executes as follows: (1)
First, it divides message intom=m1∥⋯∥mn.(2)
Then, it checks whether the tupleFn∥i∥k∥Vi,di,hi exists in the H-list:
(a)
if there existsdi=1 for i=1 to n, it aborts.(b)
ifdi=0 for i=1 to n, it computes (7)δi=gati∏j=1sgari=HFn∥i∥k∥Vi∏j=1suimija.(3)
Otherwise, it makes a Hash Query withFn∥i∥k∥Vi,di,hi and executes as above.
Challenge. The adversary adv chooses a subset I⊆1,…,n of indices of the data blocks such that at least one index in set I satisfies di=1 in the tuple Fn∥i∥k∥Vi,di,hi. And ∀i∈I one has queried the hash oracle before.
The challenge sets the challenge informationchal=i,si∣i∈I and sends it to the adversary.Proof.
Finally, the adversary outputs the response asP1∗,P2∗.
If the adversary wins the above game, the returned proof informationP1∗,P2∗ can pass the verification, which means that P1∗,P2∗ should satisfy (8)eP2∗,g=e∏i,si∈I∏k=1numiHFn∥i∥k∥Visi∏j=1sujp1j∗,v,where p1j=∑k=1tp1kjmodp‍ for j=1 to s.
Without loss of generality, we assume that there is indexi∗∈I whose di=0 in the H-list and the other index j∈I/i∗ satisfies dj=0. For simplicity, we assume all di∗j=1 of HFn∥i∗∥k∥Vj.
Thus, we have(9)eP2∗,g=e∏i,si∈I∏k=1numiHFn∥i∥k∥Visi∏j=1sujp1j∗,v=e∏i,si∈I∏k=1numiHFn∥i∥k∥Visi∏j=1sujp1j∗,v=egb∑k=1sumi∗si∗ti∗k∏i,si∈I/i∗·∏k=1numigtiksi∏j=1sujp1j∗,v.
It means that(10)gab=P2∗∏k=1numigatiksi∏i,si∈I/i∗∏j=1sgrjp1j∗.
It means that the solution of the CDH problem can be solved.
From the above simulation, we know whetherB could output the correct solution of CDH problem depends on whether the simulation aborts during the TagGen Query and Challenge phases and whether the adversary could output a valid proof information for the challenge information. The adversary is allowed to make the Hash Query at most q times. Nonabort probability during TagGen Query phase requires that all dj=0 for j=1 to s; thus its probability is τs. Nonabort probability during Challenge phase requires that at least one index i∗’s  di∗=1; thus, its probability is at least 1-ττl-1, where l is the size of subset I. Thus, its success probability is (11)ϵ>1-ττl-1τs.
Whenτ=1/q, then (12)ϵ>1-1q1qs+l-1.
This completes our proof.


### 4.2. Performance Analysis

We prototyped our algorithm and the evaluation is conducted on a desktop with Intel Core 2 Duo CPU @2.66 GHz, running Ubuntu 10.10 in Oracle VM VirtualBox Version 4.2.10 configured with 2 GB memory, and adopted PBC library to implement the crypto primitives. The security parameter of the bilinear pairing function is configured as80, which means the prime number p is 160 bits. In the evaluation, we set the file size as 80 KB, 160 KB, and 320 KB, respectively. The result of evaluation is illustrated in Table 1.Table 1
Evaluation results of our approach.
Size (bits)
Blocks (#)
Sectors (#)
Challenge blocks (#)
T
P
r
e (s)
T
G
c
h (us)
T
G
p
r (ms)
T
V
e
r (ms)
80
64
64
32
24.223
20
3121
1063
80
32
128
16
23.326
15
154
1223
80
16
256
8
25.352
18
81
1414
320
128
128
64
84.337
29
927
1671
320
64
256
32
81.216
19
512
2085
320
32
512
16
84.164
16
305
2847
1280
256
256
128
330
44
4950
3289
1280
128
512
64
336
119
9110
6761
T
P
r
e is the time cost for preprocessing; TGch is the time cost for generating challenge; TGpr is the time cost for generating proof; TVer is the time cost for verification.The experiment results shown in Table1 illustrate that the time cost of preprocessing and challenge generating will not be influenced by the number of file blocks. The time cost of proof generating decreases with the decline of N, the number of file blocks; in contrast the time cost of verification will increase when N decreases. The time cost of preprocessing increases proportionally with the increase of file size. When file size increases, the challenge generation time cost almost remains unchanged and the time cost of proof generating and verification increases.


## 4.1. Security Analysis

In this section, we prove two properties to ensure data integrity under our scheme.Theorem 1.
Correctness. If all CSP servers keep user’s data correctly, they can successfully pass the challenge-response verification procedure initiated by the user.Proof.
To verify the data correctness, according to step(7), the use computes eP2,g. It can be noticed in step (5)-(6) that P1j=∑k=1tP1kjmodpj=1,2,…,s and P2=∏k=1tP2k, where p1kj=∑mi∈CSPkaimijmodpj=1,…,s and p2k=∏mi∈CSPkσixai∈G.
According to the bilinear property of the Weil-paring function, we get(5)eP2,g=e∏k=1tP2k,g=e∏k=1t∏mi∈CSPkσixai,g=e∏k=1t∏mi∈CSPkHFn∥i∥k∥Vi·∏j=1sujmijaiα,g=e∏k=1t∏mi∈CSPkHFn∥i∥k∥Vi·∏j=1sujmijai,gα=e∏i,ai∈Q∏k=1numiHFn∥i∥k∥Viai∏j=1suj∑k=1t∑mi∈CSPkaimij,v=e∏i,ai∈Q∏k=1numiHFn∥i∥k∥Viai∏j=1sujp1j,v.
This completes our proof.Theorem 2.
If there exists a probabilistic polynomial time adversary adv and it is able to successfully convince the TPA to accept the fake proof information for a corrupted file in nonnegligible probability, then it is possible to construct a polynomial algorithmB to solve the computational Diffie-Hellman (CDH) problem by invoking adv with nonnegligible probability.Proof.
Suppose that the algorithmB is given an instance of the CDH problem tuple shown as follows:(6)g,ga,gb and its goal is to compute gab. The algorithm B will execute an interactive game with adv in the following game of security model.
Setup. Let v=ga be the public key of the user, and choose a hash function H:0,1∗→G which acts as random oracle in the following security proof. And for i=1 to s, it randomly selects ri to set ui=gri. Finally, it returns the public parameter params=p,G,g,u1,…,us,H to the adversary adv.
Hash Query. At any time, the adversary adv is able to adaptively query hash oracle for the string Fn∥i∥k∥Vi it submits. And to respond to these queries, the algorithm maintains an H-list which is initially empty and responds as follows: (1)
IfFn∥i∗∥k∥Vi,∗,∗ exists in the H-list, B retrieves the tuple Fn∥i∗∥k∥Vi,di,hi and sends hi the adversary adv.(2)
Otherwise,B chooses a bit di∈0,1 according to a bivariate distribution function Pr⁡di=0=τ and Pr⁡di=1=1-τ, where τ is a fixed probability value which will be determined later. Then B answers as follows:
(a)
Ifdi=0, B chooses a random number ti to compute hi=gti and return hi to the adversary. Then B inserts the tuple Fn∥i∗∥k∥Vi,di,hi to the H-list.(b)
Ifdi=1, B chooses a random number ti to compute hi=gbti and return hi to the adversary. Then B inserts the tuple Fn∥i∗∥k∥Vi,di,hi to the H-list.
TagGen Oracle. At any time, the adversary can adaptively query the TagGen oracle with message m. To respond to it, B executes as follows: (1)
First, it divides message intom=m1∥⋯∥mn.(2)
Then, it checks whether the tupleFn∥i∥k∥Vi,di,hi exists in the H-list:
(a)
if there existsdi=1 for i=1 to n, it aborts.(b)
ifdi=0 for i=1 to n, it computes (7)δi=gati∏j=1sgari=HFn∥i∥k∥Vi∏j=1suimija.(3)
Otherwise, it makes a Hash Query withFn∥i∥k∥Vi,di,hi and executes as above.
Challenge. The adversary adv chooses a subset I⊆1,…,n of indices of the data blocks such that at least one index in set I satisfies di=1 in the tuple Fn∥i∥k∥Vi,di,hi. And ∀i∈I one has queried the hash oracle before.
The challenge sets the challenge informationchal=i,si∣i∈I and sends it to the adversary.Proof.
Finally, the adversary outputs the response asP1∗,P2∗.
If the adversary wins the above game, the returned proof informationP1∗,P2∗ can pass the verification, which means that P1∗,P2∗ should satisfy (8)eP2∗,g=e∏i,si∈I∏k=1numiHFn∥i∥k∥Visi∏j=1sujp1j∗,v,where p1j=∑k=1tp1kjmodp‍ for j=1 to s.
Without loss of generality, we assume that there is indexi∗∈I whose di=0 in the H-list and the other index j∈I/i∗ satisfies dj=0. For simplicity, we assume all di∗j=1 of HFn∥i∗∥k∥Vj.
Thus, we have(9)eP2∗,g=e∏i,si∈I∏k=1numiHFn∥i∥k∥Visi∏j=1sujp1j∗,v=e∏i,si∈I∏k=1numiHFn∥i∥k∥Visi∏j=1sujp1j∗,v=egb∑k=1sumi∗si∗ti∗k∏i,si∈I/i∗·∏k=1numigtiksi∏j=1sujp1j∗,v.
It means that(10)gab=P2∗∏k=1numigatiksi∏i,si∈I/i∗∏j=1sgrjp1j∗.
It means that the solution of the CDH problem can be solved.
From the above simulation, we know whetherB could output the correct solution of CDH problem depends on whether the simulation aborts during the TagGen Query and Challenge phases and whether the adversary could output a valid proof information for the challenge information. The adversary is allowed to make the Hash Query at most q times. Nonabort probability during TagGen Query phase requires that all dj=0 for j=1 to s; thus its probability is τs. Nonabort probability during Challenge phase requires that at least one index i∗’s  di∗=1; thus, its probability is at least 1-ττl-1, where l is the size of subset I. Thus, its success probability is (11)ϵ>1-ττl-1τs.
Whenτ=1/q, then (12)ϵ>1-1q1qs+l-1.
This completes our proof.


## 4.2. Performance Analysis

We prototyped our algorithm and the evaluation is conducted on a desktop with Intel Core 2 Duo CPU @2.66 GHz, running Ubuntu 10.10 in Oracle VM VirtualBox Version 4.2.10 configured with 2 GB memory, and adopted PBC library to implement the crypto primitives. The security parameter of the bilinear pairing function is configured as80, which means the prime number p is 160 bits. In the evaluation, we set the file size as 80 KB, 160 KB, and 320 KB, respectively. The result of evaluation is illustrated in Table 1.Table 1
Evaluation results of our approach.
Size (bits)
Blocks (#)
Sectors (#)
Challenge blocks (#)
T
P
r
e (s)
T
G
c
h (us)
T
G
p
r (ms)
T
V
e
r (ms)
80
64
64
32
24.223
20
3121
1063
80
32
128
16
23.326
15
154
1223
80
16
256
8
25.352
18
81
1414
320
128
128
64
84.337
29
927
1671
320
64
256
32
81.216
19
512
2085
320
32
512
16
84.164
16
305
2847
1280
256
256
128
330
44
4950
3289
1280
128
512
64
336
119
9110
6761
T
P
r
e is the time cost for preprocessing; TGch is the time cost for generating challenge; TGpr is the time cost for generating proof; TVer is the time cost for verification.The experiment results shown in Table1 illustrate that the time cost of preprocessing and challenge generating will not be influenced by the number of file blocks. The time cost of proof generating decreases with the decline of N, the number of file blocks; in contrast the time cost of verification will increase when N decreases. The time cost of preprocessing increases proportionally with the increase of file size. When file size increases, the challenge generation time cost almost remains unchanged and the time cost of proof generating and verification increases.


## 5. Related Work

Based on different properties of the proposed models or schemes, related work can be classified as static data verification schemes, integrity verification schemes supporting dynamic operation on data, and verification schemes in multicloud environments. In this section, we discuss the related work in detail.


### 5.1. Static Data Integrity Verification

Early research of outsourced verification focuses on static archive data. Deswarte et al. [3] are the first to propose remote data integrity verification. They proposed two solutions to this problem, one is to precompute hash value of files and compare whether the hash value returned by server is equivalent to that of the local storage; this solution could significantly reduce the communication bandwidth between users and the server to O1. Another solution, which is based on RSA signature, requires users to sign the data before it is outsourced with the labels at the server side. Challenges could be issued randomly in the process of verification, and the bandwidth is O1. The computational cost of the server is On (n is the number of the file blocks), which increases linearly with respect to the file size.Gazzoni Filho and Barreto [4] proposed a remote data integrity verification scheme by combining RSA signature and hash function techniques. Their method could verify the same file for unlimited times, but the whole package of data is required to conduct a specific verification.Sebe et al. [12] proposed a new integrity verification scheme based on Diffie-Hellman key exchange. In their scheme, the computational overhead at the user and server sides is O1, while the storage cost at the user side, On, increases linearly with respect to the entire data size. Their follow-up work [13] combines Diffie-Hellman key exchange and RSA signature to realize remote data integrity verification.To reduce computational overhead, Ateniese et al. [5, 14] propose a probabilistic remote data integrity checking scheme calledprovable data possession (PDP) by using homomorphic verification tags andsampling technique.Ateniese et al. [6] proposed a framework to adopt homomorphism identification protocol in data integrity verification and they demonstrated this under the instance of homomorphism identification authentication protocol by Shoup [15]. The authors define the model of homomorphism identification authentication, the model of data integrity verification, and the corresponding attack models.The schemes above can only detect whether data is properly stored but could not correct the mistakes (like retrieving the data). Another branch of remote data integrity checking focuses on the error correction and retrievability along with the cloud data audition.Therefore, the study emphasis lies on data error correction and retrieval along with data integrity verification.Juels and Kaliski Jr. [16] combined data possession checking and error correction of coding technique and became the first to propose the model of POR (proof of retrievability) for remote storage of data. This model adds indistinguishable sentinel to the original code which is not only able to preserve data integrity, and data availability is also realized. Their scheme is used to handle encrypt data.Shacham and Waters [17] proposed two types of POR schemes: one is a public authentication scheme based on BLS signature, the other is private authentication on the basis of pseudorandom function, and both of the schemes have low interactions and computations. Bowers et al. [18, 19] introduced POR scheme in distributed static data storage system and realized and practiced it.Naor and Rothblum [20] study the issue of whether files are damaged badly when they are stored in remoter server. They firstly focus on the entire file correcting error code, then compute message authentication code (MAC) for every data block to verify its integrity. When the integrity is damaged and it is within the range of correcting error, then the error detection and correction are to be realized.Xu and Chang [21] proposed a high efficiency POR scheme, in which data block is involved with s group elements and L child data blocks, the storage overhead is 1/S of the file block, and computational costs is Os.In addition, for the static data in cloud, multiple integrity verification schemes have been proposed which support public verification and users’ privacy preservation. In the cloud storage users worry that data in the cloud server is damaged; on the other hand, they worry about the leakage of their data to the unauthorized third party especially for the sensitive information such as personal health report, corporation financial report. Therefore, to preserve privacy the most direct method is that users preprocess the data to encrypt it before they store the sensitive data into the cloud. With data integrity detection scheme, they could verify the data at any time.Shah et al. [22] considered the problem raised by integrity verification of data storage after it is encrypted and proposed an effective solution. The trusted third-party verdict is introduced; on one hand this is for servers reputation to attract more users by concealing the truth of losing data; on the other hand, users may mistake their own fault of losing data as that of the servers, and their server wants to avoid this situation. Considering that the average users could not preserve their secret information for a long time, shah proposed storing the users’ data along with the keys in the cloud, and hence the data integrity verification is needed as well as the key authentication. In the meantime, to not let the key be leaked to the third party, the article adopts multiple zero-knowledge proving [22] scheme to conduct key authentication.Wang et al. [23] proposed a scheme to ensure public authentication and privacy preservation. The scheme is based on the discrete logarithm zero-knowledge proof scheme combined with bilinear pairing signature. The trusted third party cannot access any outsourced data in a half honesty state. Moreover, their scheme ensures the batch verification property.


### 5.2. Integrity Verification That Supports Dynamic Data Operation

Ateniese et al. [24] presented an EPDP solution based on symmetric cryptographic algorithm. They use MAC to get the hash values of data blocks and keep them locally. They illustrate that even if the users save 70 trillion outsourced data, the local users just need to save 128 M bit data. If verifying the integrity every 15 minutes, the saved hashed data are enough to use 16 years. They divide the data to blocks so that when the cloud data are modified by some operations such as updating, deleting, and adding, they do not need to download all data to calculate the hash values and they just need to operate on certain blocks.Wang et al. [25] presented a solution that adds a preprocessing by RS codes. When users find that the data are incorrect, they can retrieve their data and correct t=d-1/2 errors, in which d is the minimum code distance. Although EPDP and Wang’s solutions can support some dynamic data operation, they still can not achieve full dynamic maintenance and their performance overheads are relatively high for data addition operation.Erway et al. [26] first discussed the complete dynamic operation problem. They used memory detection [27] and skip-lists [28] related technology to support the DPDP and improve the security. They proved that, under the standard module, this solution is more completeness and robustness than the PDP solution which is based on random oracle module. This solution also causes performance overhead. Its computing overhead and communication overhead have the Olog⁡n relationship with file size.Wang et al. [7] also proposed a solution that supports the DPDP. However, their solution is limited in data updating, deleting, and appending. It is going to be very complicated when inserting data. In their follow-up work, they combined the bilinear pairing BLS signature [29] and Merkle Hash Tree integrity verification technology [30]. They assigned the data to a binary tree and signed the leave nodes to realize dynamic operation on data blocks. Their scheme supports the public authentication and its computational and communication overhead are Olog⁡n, where n is the file size. Yuan and Yu [31] proposed a public integrity auditing scheme to support dynamic data sharing with multiuser maintenance.Hao et al. [32] proposed a privacy protected solution that supports dynamic data operations. In this solution, the interaction data size is O1 while both the local saved data size and the server computing overhead are On (in which n is the saving data size).Zheng and Xu [10] presented the FD-POR module that supports dynamic operations. Their module is based on 2-3 trees, which is a verified data structure, combined with an incremental signature method, which is also called hash signature. However, this solution cannot support public authentication.


### 5.3. Privacy Preserving in Cloud Data Checking

Ensuring the data auditing without any unnecessary information leakage is a critical concern in the practical application. Yu et al. [33] introduced the term,zero-knowledge privacy, to define the goal of privacy preserving in data integrity verification, which ensures that the TPA cannot obtain any additional information of file content from all the auxiliary verification information available. Fan et al. [34] proposed an indistinguishability-game-based definition,IND-Privacy, to evaluate the cloud data privacy preserving. They point out that many approaches are not theoretically secure according to the IND-Privacy definition. They also presented their example protocol that ensures content-integrity checking and satisfies the IND-Privacy.


### 5.4. Integrity Verification on Multicloud

By the extensive use of cloud storage, people start to consider saving their data among more than one cloud service provider. The integrity verification of multicloud becomes especially important [10].Zhu et al. [9] proposed a scheme called CPDP that can achieve the integrity authentication of multicloud. The security of CPDP mechanism is based on zero-knowledge proof system. The verifier connects with the organizer, which may reduce the communication overhead and provide computing flexibility for the verifier. However, the protocol is found to be vulnerable by Wang and Zhang [35]. Any malicious CSP or organizer can generate response that can pass the authentication, even when it has already deleted all the data. Therefore, it does not have soundness guarantee. Wang [36] presented ID-DPDP (identity-based distributed provable data possession) scheme. Under the standard CDH problem assumption, the scheme is provably secure and can support regular verification, delegate verification, and public verification as well.We present the theoretical comparison of various schemes in Table2. In summary, our scheme has the following features: fast computation speed, low storage overhead, low bandwidth requirement, and support for sampling, unlimited challenge-response interactions.Table 2
Theoretical analysis of various solutions.
Property
Scheme
Communication
Computation
Storage
Type
Unbounded
Error correct
Batch verify
Client
Server
Client
Server
PDP [5]
O
(
1
)
O
(
c
)
O
(
c
)
O
(
1
)
O
(
n
)
Pr.
√
×
×
RIC [3]
O
(
1
)
O
(
1
)
O
(
n
)
O
(
t
)
O
(
n
)
Det.
√
×
×
POR [16]
O
(
1
)
O
(
1
)
O
(
c
)
O
(
t
)
O(n+k)
Pr.
×
√
×
CPOR [17]
O(1)
O(c)
O(c)
O(1)
O(n+k)
Pr.
√
√
×
DPDP [6]
O(log⁡n)
O(log⁡n)
O(log⁡n)
O(1)
O(n)
Pr.
√
×
×
CPDP [9]
O(1)
O(c)
O(c)
O(t)
O(n)
Pr.
×
×
×
Wang [37]
O(log⁡n)
O(log⁡n)
O(log⁡n)
O(1)
O(n)
Pr.
√
×
×
Hao [32]
O(1)
O(1)
O(c)
O(n)
O(n)
Det.
√
×
×
Our Scheme
O(1)
O(c)
O(c)
O(1)
O(n)
Pr.
√
×
√
t is the verification time allowed by the scheme; Type means guarantee types provided by the scheme; Det. and Pr. represent Deterministic guarantee and Probabilistic guarantee, respectively; n is the number of the file blocks.Redundancy Analysis. Basically, there are three ways to ensure the remote cloud storage audition, that is, hash-function-based solutions, homomorphic-authentication-tag-based solutions, and network-coding-based solutions. All these approaches will cause unavoidable redundancy and thus additional storage overhead at the server side. Furthermore, there are potential security vulnerabilities in hash-function-based solutions, while network-coding-based solutions cause higher storage overhead than homomorphic-authentication-tag-based solutions. In our scheme, we create the authentication tags based on Boneh-Lynn-Shacham (BLS) signature, whose additional redundancy is p bits for one file block. In contrast, in Zhu’s scheme [9], their storage redundancy for authentication tag per file block is also p bits; the redundancy caused by Wang’s approach [35] is H·+p bits per file block; and the approach proposed by Yuan and Yu [31] introduced p-bit additional storage overhead at the server side to verify one file block. Compared with existing related solutions, the redundancy rate introduced by our scheme is relative low.


## 5.1. Static Data Integrity Verification

Early research of outsourced verification focuses on static archive data. Deswarte et al. [3] are the first to propose remote data integrity verification. They proposed two solutions to this problem, one is to precompute hash value of files and compare whether the hash value returned by server is equivalent to that of the local storage; this solution could significantly reduce the communication bandwidth between users and the server to O1. Another solution, which is based on RSA signature, requires users to sign the data before it is outsourced with the labels at the server side. Challenges could be issued randomly in the process of verification, and the bandwidth is O1. The computational cost of the server is On (n is the number of the file blocks), which increases linearly with respect to the file size.Gazzoni Filho and Barreto [4] proposed a remote data integrity verification scheme by combining RSA signature and hash function techniques. Their method could verify the same file for unlimited times, but the whole package of data is required to conduct a specific verification.Sebe et al. [12] proposed a new integrity verification scheme based on Diffie-Hellman key exchange. In their scheme, the computational overhead at the user and server sides is O1, while the storage cost at the user side, On, increases linearly with respect to the entire data size. Their follow-up work [13] combines Diffie-Hellman key exchange and RSA signature to realize remote data integrity verification.To reduce computational overhead, Ateniese et al. [5, 14] propose a probabilistic remote data integrity checking scheme calledprovable data possession (PDP) by using homomorphic verification tags andsampling technique.Ateniese et al. [6] proposed a framework to adopt homomorphism identification protocol in data integrity verification and they demonstrated this under the instance of homomorphism identification authentication protocol by Shoup [15]. The authors define the model of homomorphism identification authentication, the model of data integrity verification, and the corresponding attack models.The schemes above can only detect whether data is properly stored but could not correct the mistakes (like retrieving the data). Another branch of remote data integrity checking focuses on the error correction and retrievability along with the cloud data audition.Therefore, the study emphasis lies on data error correction and retrieval along with data integrity verification.Juels and Kaliski Jr. [16] combined data possession checking and error correction of coding technique and became the first to propose the model of POR (proof of retrievability) for remote storage of data. This model adds indistinguishable sentinel to the original code which is not only able to preserve data integrity, and data availability is also realized. Their scheme is used to handle encrypt data.Shacham and Waters [17] proposed two types of POR schemes: one is a public authentication scheme based on BLS signature, the other is private authentication on the basis of pseudorandom function, and both of the schemes have low interactions and computations. Bowers et al. [18, 19] introduced POR scheme in distributed static data storage system and realized and practiced it.Naor and Rothblum [20] study the issue of whether files are damaged badly when they are stored in remoter server. They firstly focus on the entire file correcting error code, then compute message authentication code (MAC) for every data block to verify its integrity. When the integrity is damaged and it is within the range of correcting error, then the error detection and correction are to be realized.Xu and Chang [21] proposed a high efficiency POR scheme, in which data block is involved with s group elements and L child data blocks, the storage overhead is 1/S of the file block, and computational costs is Os.In addition, for the static data in cloud, multiple integrity verification schemes have been proposed which support public verification and users’ privacy preservation. In the cloud storage users worry that data in the cloud server is damaged; on the other hand, they worry about the leakage of their data to the unauthorized third party especially for the sensitive information such as personal health report, corporation financial report. Therefore, to preserve privacy the most direct method is that users preprocess the data to encrypt it before they store the sensitive data into the cloud. With data integrity detection scheme, they could verify the data at any time.Shah et al. [22] considered the problem raised by integrity verification of data storage after it is encrypted and proposed an effective solution. The trusted third-party verdict is introduced; on one hand this is for servers reputation to attract more users by concealing the truth of losing data; on the other hand, users may mistake their own fault of losing data as that of the servers, and their server wants to avoid this situation. Considering that the average users could not preserve their secret information for a long time, shah proposed storing the users’ data along with the keys in the cloud, and hence the data integrity verification is needed as well as the key authentication. In the meantime, to not let the key be leaked to the third party, the article adopts multiple zero-knowledge proving [22] scheme to conduct key authentication.Wang et al. [23] proposed a scheme to ensure public authentication and privacy preservation. The scheme is based on the discrete logarithm zero-knowledge proof scheme combined with bilinear pairing signature. The trusted third party cannot access any outsourced data in a half honesty state. Moreover, their scheme ensures the batch verification property.


## 5.2. Integrity Verification That Supports Dynamic Data Operation

Ateniese et al. [24] presented an EPDP solution based on symmetric cryptographic algorithm. They use MAC to get the hash values of data blocks and keep them locally. They illustrate that even if the users save 70 trillion outsourced data, the local users just need to save 128 M bit data. If verifying the integrity every 15 minutes, the saved hashed data are enough to use 16 years. They divide the data to blocks so that when the cloud data are modified by some operations such as updating, deleting, and adding, they do not need to download all data to calculate the hash values and they just need to operate on certain blocks.Wang et al. [25] presented a solution that adds a preprocessing by RS codes. When users find that the data are incorrect, they can retrieve their data and correct t=d-1/2 errors, in which d is the minimum code distance. Although EPDP and Wang’s solutions can support some dynamic data operation, they still can not achieve full dynamic maintenance and their performance overheads are relatively high for data addition operation.Erway et al. [26] first discussed the complete dynamic operation problem. They used memory detection [27] and skip-lists [28] related technology to support the DPDP and improve the security. They proved that, under the standard module, this solution is more completeness and robustness than the PDP solution which is based on random oracle module. This solution also causes performance overhead. Its computing overhead and communication overhead have the Olog⁡n relationship with file size.Wang et al. [7] also proposed a solution that supports the DPDP. However, their solution is limited in data updating, deleting, and appending. It is going to be very complicated when inserting data. In their follow-up work, they combined the bilinear pairing BLS signature [29] and Merkle Hash Tree integrity verification technology [30]. They assigned the data to a binary tree and signed the leave nodes to realize dynamic operation on data blocks. Their scheme supports the public authentication and its computational and communication overhead are Olog⁡n, where n is the file size. Yuan and Yu [31] proposed a public integrity auditing scheme to support dynamic data sharing with multiuser maintenance.Hao et al. [32] proposed a privacy protected solution that supports dynamic data operations. In this solution, the interaction data size is O1 while both the local saved data size and the server computing overhead are On (in which n is the saving data size).Zheng and Xu [10] presented the FD-POR module that supports dynamic operations. Their module is based on 2-3 trees, which is a verified data structure, combined with an incremental signature method, which is also called hash signature. However, this solution cannot support public authentication.


## 5.3. Privacy Preserving in Cloud Data Checking

Ensuring the data auditing without any unnecessary information leakage is a critical concern in the practical application. Yu et al. [33] introduced the term,zero-knowledge privacy, to define the goal of privacy preserving in data integrity verification, which ensures that the TPA cannot obtain any additional information of file content from all the auxiliary verification information available. Fan et al. [34] proposed an indistinguishability-game-based definition,IND-Privacy, to evaluate the cloud data privacy preserving. They point out that many approaches are not theoretically secure according to the IND-Privacy definition. They also presented their example protocol that ensures content-integrity checking and satisfies the IND-Privacy.


## 5.4. Integrity Verification on Multicloud

By the extensive use of cloud storage, people start to consider saving their data among more than one cloud service provider. The integrity verification of multicloud becomes especially important [10].Zhu et al. [9] proposed a scheme called CPDP that can achieve the integrity authentication of multicloud. The security of CPDP mechanism is based on zero-knowledge proof system. The verifier connects with the organizer, which may reduce the communication overhead and provide computing flexibility for the verifier. However, the protocol is found to be vulnerable by Wang and Zhang [35]. Any malicious CSP or organizer can generate response that can pass the authentication, even when it has already deleted all the data. Therefore, it does not have soundness guarantee. Wang [36] presented ID-DPDP (identity-based distributed provable data possession) scheme. Under the standard CDH problem assumption, the scheme is provably secure and can support regular verification, delegate verification, and public verification as well.We present the theoretical comparison of various schemes in Table2. In summary, our scheme has the following features: fast computation speed, low storage overhead, low bandwidth requirement, and support for sampling, unlimited challenge-response interactions.Table 2
Theoretical analysis of various solutions.
Property
Scheme
Communication
Computation
Storage
Type
Unbounded
Error correct
Batch verify
Client
Server
Client
Server
PDP [5]
O
(
1
)
O
(
c
)
O
(
c
)
O
(
1
)
O
(
n
)
Pr.
√
×
×
RIC [3]
O
(
1
)
O
(
1
)
O
(
n
)
O
(
t
)
O
(
n
)
Det.
√
×
×
POR [16]
O
(
1
)
O
(
1
)
O
(
c
)
O
(
t
)
O(n+k)
Pr.
×
√
×
CPOR [17]
O(1)
O(c)
O(c)
O(1)
O(n+k)
Pr.
√
√
×
DPDP [6]
O(log⁡n)
O(log⁡n)
O(log⁡n)
O(1)
O(n)
Pr.
√
×
×
CPDP [9]
O(1)
O(c)
O(c)
O(t)
O(n)
Pr.
×
×
×
Wang [37]
O(log⁡n)
O(log⁡n)
O(log⁡n)
O(1)
O(n)
Pr.
√
×
×
Hao [32]
O(1)
O(1)
O(c)
O(n)
O(n)
Det.
√
×
×
Our Scheme
O(1)
O(c)
O(c)
O(1)
O(n)
Pr.
√
×
√
t is the verification time allowed by the scheme; Type means guarantee types provided by the scheme; Det. and Pr. represent Deterministic guarantee and Probabilistic guarantee, respectively; n is the number of the file blocks.Redundancy Analysis. Basically, there are three ways to ensure the remote cloud storage audition, that is, hash-function-based solutions, homomorphic-authentication-tag-based solutions, and network-coding-based solutions. All these approaches will cause unavoidable redundancy and thus additional storage overhead at the server side. Furthermore, there are potential security vulnerabilities in hash-function-based solutions, while network-coding-based solutions cause higher storage overhead than homomorphic-authentication-tag-based solutions. In our scheme, we create the authentication tags based on Boneh-Lynn-Shacham (BLS) signature, whose additional redundancy is p bits for one file block. In contrast, in Zhu’s scheme [9], their storage redundancy for authentication tag per file block is also p bits; the redundancy caused by Wang’s approach [35] is H·+p bits per file block; and the approach proposed by Yuan and Yu [31] introduced p-bit additional storage overhead at the server side to verify one file block. Compared with existing related solutions, the redundancy rate introduced by our scheme is relative low.


## 6. Conclusion

Together with cloud-computing technology, heterogeneous wireless networking technology has become a critical infrastructure adopted by emerging communication networks. Due to the convenience, low cost, and flexibility, cloud storing techniques become widely used in remote services, such as wireless data outsourcing and resource sharing. However, users lose the physical control of their outsourced data, while the cloud storage service provider is not always trustworthy. Consequently, how to ensure the integrity of their remotely outsourced data becomes a serious concern for users to select cloud storing services. In this paper, we present a collaborative multicloud data integrity audition scheme, which is based on BLS signatures and homomorphic tags. According to the proposed scheme, users can audit their outsourced data in a one-round challenge-response process. In addition, our scheme also enables dynamic data maintenance (e.g., data modification, insertion, and deletion). The theoretical analysis demonstrates the effectiveness of our scheme and the probability that the dishonest CSP server can bypass the checking successfully is neglectable if the one-way hash function is collision-resistant and the computational Diffie-Hellman (CDH) assumption holds.



---

*Source: 2948025-2017-10-31.xml*