Efficient Dynamic Replicated Data Possession Checking in Distributed Cloud Storage Systems

Abstract

More and more organizations outsource their data to remote cloud servers (RCSs). Data owners rent the cloud service providers (CSPs) infrastructure to store their unlimited resources by paying fees metered in month or gigabyte. For increasing the availability and scalability of data, the data owners store their data replicas on multiple servers across multiple data centers. Data owners should ensure that the CSPs actually store all their copies according to the service contract. In this paper, we present an efficient dynamic multicopies possession checking scheme that has the following properties: (1) the data owner uses fully homomorphic encryption (FHE) algorithm to generate multiple copies; (2) the scheme supports data block dynamic operation; (3) the scheme supports third-party auditor's public validation. Finally, security analysis and experimental results show that our scheme can resist forgery, replacement, and replay attack and perform better than some other related scheme published recently.

1. Introduction

Storing abundant file resources in the cloud has become the current trend [1]. An increasing number of users send their data to the cloud service providers (CSPs) for storage. Storing data on the remote cloud server enables organizations to relieve the burden brought by server updating and other computing issues. Also, authorized users can conveniently use the stored data from different geographic locations. When data has been stored on a remote CS that may be unreliable, the data owners cannot control their privacy data directly. This lack of control for privacy data would exhibit data confidentiality and privacy protection problem. For the CSP, some errors may occur, such as software or hardware failures and operational errors of system administrator [2–5]. For maintaining the CSP's reputation, he/she usually tries to hide data loss incidents. Therefore, he/she may not be trustworthy. In order to deal with data confidentiality, the sensitive data is encrypted before it is outsourced to the CSP. For integrity protection, many researchers have proposed provable data possession (PDP) schemes to verify the integrity of data stored on the CSP.

For intensifying responsibility of the CSP, it is essential for the data owner to demand that the CSP provide evidence that the data owners' data are not discarded or damaged [6]. PDP [7] is a method to check integrity of the data stored on the CSP. To keep the security of data, the data owner encrypts the data file and calculates tag for encrypted data file. Then he/she stores the encrypted data blocks and the corresponding tags on the CSP and deletes them from the local computers. When the data owner (or verifier) wants to check the integrity of data file, he/she sends a challenge vector to the CSP. The CSP makes a response for challenge and sends the response to the data owner (or verifier).

How to efficiently guarantee that the CSP faithfully stores the data owner's data file is the main goal of remote PDP scheme. Nowadays, there exist two types of verification scheme: provable data possession (PDP) and Proof of Retrieval (POR). In addition, to validate the correctness of data, the POR scheme can also check out the corrupted data block and then recover the original data. In order to check the correctness of data stored on the CSP, Ateniese et al. [7, 8] proposed two provably secure PDP schemes. In the subsequent year, different variations of PDP schemes were proposed, such as [9–12] which are based on different cryptographic hard problem assumptions. In 2007, a model of POR was constructed in [13], Juels and Kaliski used error-correcting code to present a sentinel-based POR protocol. Various POR schemes that check static data file integrity can be found in [14–19].

In fact, it is not realistic to check static data file integrity, because the stored data block is usually modified by the data owner. Therefore, we consider that one of the basic requirements of storing data on the remote CSP is to support dynamic update operation of data block. The updated operation mainly refers to modification, insertion, or deletion of the stored data.

Another design goal is to support public validation. It is not appropriate to allow any side of the data owner or the CSP to verify the integrity of data stored on the CSP, because neither of them could be ensured to get unbiased verification results [20]. The third-party verifier is a suitable choice for the storage verification. A third-party verifier has the ability to do meaningful work and it is trusted by the data owners and CSPs. Under the influence of the distributed storage system, the data storage verification becomes more significant. Many schemes have been proposed: Proof of Retrieval (POR) protocols [21], remote integrity checking protocols [22, 23], and provable data possession protocols [24]. However, these protocols only apply to the scene that the data owner verifies the integrity of the data file stored on the CSP. In cloud computing, the data file storage verification is provided by a third-party rather than the data owners. Therefore, we propose a PDP scheme that supports public verifiability for data stored on the CSP and dynamic operation.

(1) Related Work. Ateniese et al. [7] first proposed a PDP paradigm and built two PDP schemes. However, they have not considered the multicopies storage system and dynamic data storage operation. To solve dynamic data operation problem, Zeng [10] and Wang et al. [20] proposed a dynamic version which can support limited data block operation but cannot support block insertions. In 2009, Erway et al. [25] modified the PDP scheme in [7] to achieve the dynamic updates of data files stored on the CSP applying rank-based authenticated skip lists. However, the computation and communication efficiency of this scheme achieves good only for a single data block. Wang et al. [20] verified the integrity of file copies using MHT. Although their scheme supports dynamic operation, their data files stored on the CSP are not encrypted and work for a single data block. In 2011, Hao et al. [26] proposed a PDP scheme which supports not only the dynamic operation for data file but also public audit. Public audit is an interaction protocol which allows any entity, not necessarily the data owner, to verify the correctness of data stored on the CSP, since their scheme also does not consider stored data file encryption and the scheme cannot be modified to support multicopies data file stored. Barsoum and Hasan [27] proposed a PDP scheme that encrypts a file F by using an encryption algorithm and generates different data file replicas. The encryption algorithm has a strong diffusion property, for example, AES. However, the data updating efficiency of their scheme is not good, for all the copies stored on the CSP will be encrypted again and updated on the CSP. To solve this problem, we use the FHE algorithm to encrypt the data file and generate multicopies stored on the CSP. The file copies need not be encrypted again when data updates. Therefore, the verification efficiency of our PDP scheme has been greatly improved.

The goal of our PDP scheme differs from the goal defined in the earlier researches. Our PDP scheme aims to keep confidentiality, integrity, and public verifiability of data copies stored on the CSP. Considering the FHE algorithm which will generate a random noise in each process, we encrypt a file F to get multiple file copies. The novelty of our scheme comes with ensuring data security and providing good efficiency for data updating while preserving the public verifiability. Because the file copies are stored on the distributed cloud server, we assume that all copies will not be damaged at the same time.

(2) Design Goal. The proposed scheme in our paper should hold the following properties simultaneously. (1) Correctness: the third-party auditor must accept all valid information proved by the cloud; (2) Public Auditing: the public auditor cannot get any information about the stored data block; (3) security goals: the proposed scheme can resist forgery attack, replacement attack, replay attack, and channel attack. The corrupted data block in corrupted copies can be checked out in this scheme. Thus, the data owner just needs to regenerate the new copy of corrupted data block instead of regenerating the whole new file copy. When the data owner needs to regenerate the valid form of corrupted data block copy, he/she first obtains the original data block from other uncorrupted data copies and then reencrypts the original data block to generate a new data block copy.

The rest of the paper is organized as follows. The preliminaries are introduced in Section 2, followed by the proposed scheme description in Section 3. Section 4 analyzes the security of our scheme. Section 5 presents the implementation and experimental result. Conclusions are given in Section 6.

2. Preliminary

Some preliminary knowledge used in our paper is introduced in this section. Let F be a file outsourced to the CSP. It is divided into a sequence of n blocks; that is, $F=\left\{b_{\mathrm{1}},\dots ,b_n\right\}$ , where $b_j\in {\mathcal{Z}}_q^{\ast }$ for some large prime q. Denote ${\tilde{F}}_i$ as the ith file copy. Thus ${\tilde{F}}_i=\left\{{\tilde{b}}_{i\mathrm{1}},\dots ,{\tilde{b}}_{in}\right\}$ , where ${\tilde{b}}_{ij}$ represents the jth file block of the ith copy.

Bilinear Map/Pairing. Denote ${\mathcal{G}}_1$ , ${\mathcal{G}}_2$ , and ${\mathcal{G}}_T$ as three cycle multiplicative groups; they have the same prime order q; that is, $\left|{\mathcal{G}}_1\right|=\left|{\mathcal{G}}_2\right|=\left|{\mathcal{G}}_T\right|=q$ . Let $e:{\mathcal{G}}_1\times {\mathcal{G}}_2\to {\mathcal{G}}_T$ be a bilinear map [2], which holds the following properties:

• (a)

bilinearity: $\forall g_{\mathrm{1}}\in {\mathcal{G}}_1,\hspace{0.17em}\hspace{0.17em}{g}_{\mathrm{2}}\in {\mathcal{G}}_2$ , and $a,b\in {\mathcal{Z}}_q$ :

$$\begin{array}{cc}& e\left(g_1^a,g_2^b\right)=e{\left(g_1,g_2\right)}^{ab};\end{array}$$

(1)

(b)

nondegeneracy: $\exists g_{\mathrm{3}}\in {\mathcal{G}}_1,\hspace{0.17em}\hspace{0.17em}{g}_{\mathrm{4}}\in {\mathcal{G}}_2$ , such that $e\left(g_{\mathrm{3}},g_{\mathrm{4}}\right)\ne 1_{{\mathcal{G}}_T}$ ;

(c)

computability: $\forall g_{\mathrm{5}}\in {\mathcal{G}}_{\mathrm{1}}$ , $g_{\mathrm{6}}\in {\mathcal{G}}_2$ ; there exists an efficient algorithm to compute $e\left(g_{\mathrm{5}},g_{\mathrm{6}}\right)$ .

Computational Diffie-Hellman (CDH) Problem. ${\mathcal{G}}_{\mathrm{1}}$ is a cyclic multiplicative group on ECC generated by $g^{\prime }$ . Given $g^{\prime a}$ and $g^{\prime b}$ with $a,b\in {\mathcal{Z}}_q$ , compute $g^{\prime ab}$ .

Our protocol involves three cryptographic functions: $h(·)$ is a map-to-point hash function, $\psi (·)$ is a pseudorandom function, and $\vartheta (·)$ is a pseudorandom permutation:

•  

$h(·)\text{:}\hspace{0.17em}{\left\{\mathrm{0,1}\right\}}^{\ast }\to {\mathcal{G}}_1$ ,

 

$\psi (·)\text{:}\hspace{0.17em}{\mathcal{Z}}_q^{\ast }\times \left\{\mathrm{1,2},\dots ,n\right\}\to {\mathcal{Z}}_q^{\ast }$ ,

 

$\vartheta (·)\text{:}\hspace{0.17em}{\mathcal{Z}}_q^{\ast }\times \left\{\mathrm{1,2},\dots ,n\right\}\to \left\{\mathrm{1,2},\dots ,n\right\}$ .

Fully Homomorphic Encryption (FHE) [28]. The FHE scheme includes the following three algorithms:

•  

KeyGen: input a security parameter λ and output three parameters $(\rho ,\eta ,\gamma )$ , where $\rho =\lambda ,\hspace{0.17em}\hspace{0.17em}\eta =\lambda ·⌈\mathrm{l}\mathrm{o}\mathrm{g}\hspace{0.17em}n⌉,\gamma =\mathrm{5}·\lambda ·⌈\mathrm{l}\mathrm{o}\mathrm{g}\hspace{0.17em}n⌉/\mathrm{2}$ . Let p be a η-bit odd integer, $p\leftarrow (\mathrm{2}\mathcal{Z}+\mathrm{1})\cap ({\mathrm{2}}^{\eta -\mathrm{1}},{\mathrm{2}}^{\eta })$ . Sign p as the secret key sk. Compute $q_{\mathrm{0}}\leftarrow (\mathrm{2}\mathcal{Z}+\mathrm{1})\cap (\mathrm{1},{\mathrm{2}}^{\gamma }/p)$ , $t_{\mathrm{0}}=q_{\mathrm{0}}·p$ . Sign $t_{\mathrm{0}}$ as the public key pk.

 

Enc: input a plaintext $m\in \{\mathrm{0,1}\}$ and the public key $t_{\mathrm{0}}$ ; choose a random integer $q^{\prime }$ from $[\mathrm{1},{\mathrm{2}}^{\gamma }/p)$ and r from $(-{\mathrm{2}}^{\rho },{\mathrm{2}}^{\rho })$ and then compute ciphertext C:

$$\begin{array}{cc}& C=E\left(m,\mathrm{p}\mathrm{k}\right)=\left(m+\mathrm{2}·r+q^{\prime }·p\right)\mathrm{m}\mathrm{o}\mathrm{d}\hspace{0.17em}{t}_{\mathrm{0}}.\end{array}$$

(2)

 

Dec: input a ciphertext C and the secret key sk and output the plaintext m:

$$\begin{array}{cc}& m=D\left(C,\mathrm{s}\mathrm{k}\right)=\left(C\mathrm{mod}p\right)\mathrm{mod}\mathrm{2}.\end{array}$$

(3)

On one hand, each homomorphic encryption generates a random noise, which is a variable. Therefore, encrypting one original file τ times with one public key will generate τ different file replicas. On the other hand, we use the homomorphic property that satisfies plaintext operation corresponding to ciphertext operation to realize dynamic operation for data replicas stored on the CSPs.

3. Dynamic Multireplicas Provable Remote Data Possession (DPRDP) Scheme

In this work, the cloud storage model considered in this paper consists of four entities as shown in Figure 1: (1) a data owner who can be an individual or an organization possesses privacy data information, (2) the CSPs provide paid storage space for storing the data owner's data files, (3) the third-party auditor is responsible for integrity verification of file copies stored on the CSP through challenge-response protocol, and (4) authorized users share the decryption key with the data owner and have the right to access the data copies from the CSP. In our paper, we mainly discuss the first three entities: the data owner, the CSP, and the third-party verifier.

Figure 1

Cloud storage system model.

3.1. DPRDP Scheme

In [29], Mukundan et al. used Paillier encryption to generate data copies. However, the encryption time complexity of their scheme is $\mathrm{2}·O((\mathrm{l}\mathrm{o}\mathrm{g}\hspace{0.17em}N{)}^{\mathrm{3}})$ ; it is a particular large number when the size of N is 1024 bits. Therefore, we choose a fully homomorphic encryption [28] with smaller time complexity than the scheme in [29] to generate the data block copies.

The proposed MR-PDP scheme includes nine functions KeyGen, CopiesGen, TagGen, Challenge, Response, Verify, Request, Execution, and IndiceRetri.

(1) KeyGen. The data owner inputs a security parameter λ and generates a public/secret key pair $(\mathrm{p}\mathrm{k},\mathrm{s}\mathrm{k})$ for encryption or decryption. Also, he/she chooses a random integer $\delta \in {\mathcal{Z}}_q$ as secret key for signature and generates a public key $Y=g^{\delta }\in {\mathcal{G}}_2$ for verification; g is the generator of ${\mathcal{G}}_2$ .

(2)CopiesGen. For a file F, the data owner creates τ differentiable copies $\mathcal{F}=\left\{{\tilde{F}}_{\mathrm{1}},\dots ,{\tilde{F}}_{\tau }\right\}$ using FHE algorithm. For copy ${\tilde{F}}_i,\hspace{0.17em}\hspace{0.17em}\mathrm{1}\le i\le \tau$ , it can be denoted as ${\tilde{F}}_i={\left\{{\tilde{b}}_{\mathrm{i}\mathrm{1}},\dots ,{\tilde{b}}_{in}\right\}}_{\mathrm{1}\le i\le \tau }$ , where ${\tilde{b}}_{ij}$ is the encryption of data block $b_j$ . Firstly, homomorphic encryption generates a random noise that is a variable. Therefore, encrypting one original data s times with a public key will generate s different data replicas. That is, even if $b_j=b_{j^{\prime }}$ , we still get ${\tilde{b}}_{ij}\ne {\tilde{b}}_{{ij}^{\prime }}$ , $\mathrm{1}\le j,j^{\prime }\le n$ , $j\ne j^{\prime }$ . Thus, the data owner can obtain different tags for the same data blocks. Secondly, we use the homomorphic property that satisfies plaintext operation corresponding to ciphertext operation to realize dynamic operation for data replicas stored on the CSPs, including data block insertion, modification, and deletion. Finally, the authorized users only need to hold a single decryption secret key sk. Upon obtaining the file copies from the CSP, the authorized users decrypt the file copies and get the original file plaintexts.

(3)TagGen. It is necessary to suppose that the data owner generates the tags sequentially in accordance with the index j. That is, the data owner generates a tag for a data block ${\tilde{b}}_{i\mathrm{2}}$ after ${\tilde{b}}_{i\mathrm{1}}$ . For data block ${\tilde{b}}_{ij}$ , $\mathrm{1}\le i\le \tau$ , $\mathrm{1}\le j\le n$ , the data owner does the following:

• (a)

choosing a random element $\omega {\in }_R{\mathcal{G}}_1$ ;

(b)

computing $T_{ij}={\left(h(F_N‖i)·{\omega }^{{\tilde{b}}_{ij}}\right)}^{\delta }\in {\mathcal{G}}_1$ , where $F_N$ is the name of file F;

(c)

outputting $T_{ij}$ ;

(d)

computing the tag $Tag$ of $\left({\tilde{b}}_{ij},T_{ij}\right)$ using the secret key δ and sending $Tag$ and $\left({\tilde{b}}_{ij},T_{ij}\right)$ to the CSP.

Upon receiving the $Tag$ and $\left({\tilde{b}}_{ij},T_{ij}\right)$ , the CSP verifies whether the block-tag pair $\left({\tilde{b}}_{ij},T_{ij}\right)$ is correct or not. If the block-tag pair $\left({\tilde{b}}_{ij},T_{ij}\right)$ is correct, the CSP stores them. Otherwise, he/she rejects them.

(4)Challenge. The data owner assigns the third auditor to complete validation tasks. For challenging the CSP and verifying the possession and integrity of all copies, the third-party auditor sends c (number of data blocks to be challenged) and two challenge keys $k_{\mathrm{1}},\hspace{0.17em}\hspace{0.17em}{k}_{\mathrm{2}}$ at each challenge stage: a pseudorandom permutation key $k_{\mathrm{1}}\in {\mathcal{Z}}_q^{\ast }$ and a pseudorandom function key $k_{\mathrm{2}}\in {\mathcal{Z}}_q^{\ast }$ . Both the CSP and the third-party auditor use ϑ keyed with $k_{\mathrm{1}}$ and ψ keyed with $k_{\mathrm{2}}$ to generate a set $S=\left\{\left(j^{\prime },r_{j^{\prime }}\right)\right\}$ of c pairs of random indices and their random values, where $r_{j^{\prime }}={\psi }_{k_{\mathrm{2}}}(t{)}_{1\le t\le c}$ , $j^{\prime }={\vartheta }_{k_{\mathrm{1}}}(t{)}_{\mathrm{1}\le t\le c}$ . The random index $j^{\prime }$ indicates the physical positions of c data blocks to be challenged. Let the challenge be a triple $\left(c,k_{\mathrm{1}},k_{\mathrm{2}}\right)$ .

(5)Response. The CSP receives the triple $\left(c,k_{\mathrm{1}},k_{\mathrm{2}}\right)$ and computes random indices $j^{\prime }$ and random values $r_{j^{\prime }}$ . After obtaining the values of $j^{\prime }$ and $r_{j^{\prime }}$ , the CSP does the following:

• (a)

computing $T={\prod }_{(j^{\prime },r_{j^{\prime }})\in S}{T}_{j^{\prime }}^{r_{j^{\prime }}}$ , where $T_{j^{\prime }}={\prod }_{i=\mathrm{1}}^{\tau }{T}_{i{j}^{\prime }}\in {\mathcal{G}}_1$ ;

(b)

computing ${\xi }_i={\sum }_{(j^{\prime },r_{j^{\prime }})\in S}{r}_{j^{\prime }}·{\tilde{b}}_{i{j}^{\prime }}\in {\mathcal{Z}}_p$ , $\xi ={\left\{{\xi }_i\right\}}_{\mathrm{1}\le i\le \tau }$ ;

(c)

sending $\left(T,\xi \right)$ to the verifier.

(6)Verify. After receiving the proof $\left(T,\xi \right)$ from the CSP, the third-party auditor checks the following verification equation:

$$\begin{array}{cc}& e\left(T,g\right)\stackrel{?}{=}e\left({{\displaystyle \prod }}_{\left(j^{\prime },r_{j^{\prime }}\right)\in S}\hspace{0.17em}{\displaystyle \prod }_{i=1}^{\tau }h{\left(F_N‖i\right)}^{r_{j^{\prime }}}·{\omega }^{{\sum }_{i=1}^{\tau }{\xi }_i},Y\right).\end{array}$$

(4)

If the above equation holds, the third-party auditor outputs 1, otherwise 0.

The challenge-response protocol between the third-party auditor and the CSP in the DPRDP scheme is summarized in Figure 2.

Figure 2

The challenge-response protocol in the DPRDP scheme.

(7)Request. When the data owner wants to update the data block stored on the CSP, he/she would generate an update requirement including file name, update command, update index, and encrypted difference and update tag. The data owner sends the update request $\left(F_N,\mathrm{R}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{t},j,\mathrm{F}\mathrm{H}\mathrm{E}(\Delta b_j),T_{ij}^{\prime }\right)$ to the CSP, where Request denotes update request that may be modification, deletion, or insertion, j is the index of the updated data block, $\mathrm{F}\mathrm{H}\mathrm{E}(\Delta b_j)$ is the encryption of difference between the original data block and the updated data block, and $T_{ij}^{\prime }$ is the updated tag. The data block modification includes data block addition and multiplication.

(8)Execution. The CSP receives the update request and executes the update operation. He/she inputs the copies of file F, the tag T, and update request and outputs the copies of an updated file $F^{\prime }$ and its new tag $T^{\prime }$ . Upon completing the block data update operation, the third-party auditor executes the verification protocol to confirm that the CSP has implemented the update operation correctly. We give a detailed data block modification procedure in Figure 3.

Figure 3

Data block modification operation procedure in the DPRDP scheme.

The data block insertion and deletion operations are similar with the data block modification. In order to complete the data block insertion, the data owner inserts a new data block before position j in a copy file. Thus, the number of data blocks in copies will be changed from n to $n+\mathrm{1}$ . The data owner chooses an inserted data block $b_j^{\prime }$ and encrypts it using FHE algorithm. Also, the data owner calculates a new tag $T_{ij}^{\prime }$ for the inserted data block ciphertext ${\tilde{b}}_{ij}^{\prime }$ of $b_j^{\prime }$ and then sends $\left(F_N,\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{e}\mathrm{r}\mathrm{t},j_{\mathrm{b}\mathrm{e}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}},E(b_j^{\prime }),T_{ij}^{\prime }\right)$ and two keys $k_{\mathrm{1}}$ , $k_{\mathrm{2}}$ to the CSP. Upon getting these elements, the CSP inserts the new data block ciphertext ${\tilde{b}}_{ij}^{\prime }$ before position j in copy file ${\tilde{F}}_i$ , $\mathrm{1}\le i\le \tau$ . Hence, the inserted file copy can be represented as ${\tilde{F}}_i^{\prime }=\left\{{\tilde{b}}_{i1},\dots ,{\tilde{b}}_{ij-1},{\tilde{b}}_{ij}^{\prime },{\tilde{b}}_{ij},\dots ,{\tilde{b}}_{in}\right\}$ and the new data block-tag set can be denoted as $\left\{{\prod }_{i=\mathrm{1}}^{\tau }{T}_{i\mathrm{1}},\dots ,{\prod }_{i=\mathrm{1}}^{\tau }{T}_{ij-\mathrm{1}},{\prod }_{i=\mathrm{1}}^{\tau }{T}_{ij}^{\prime },{\prod }_{i=\mathrm{1}}^{\tau }{T}_{ij},\dots ,{\prod }_{i=\mathrm{1}}^{\tau }{T}_{in}\right\}$ . Finally, the CSP makes a response with the auditor to prove that he/she correctly performs the insertion operation. Data block deletion is opposite to the insertion operation. Upon deleting a data block, the number of file data blocks will be changed from n to $n-\mathrm{1}$ . If the data owner wants to delete the jth block from each copy, he/her sends a delete command $\left(F_N,\mathrm{D}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e},j,\Theta ,\Theta \right)$ to the CSP, where Θ denotes empty element. After receiving this command, the CSP deletes the data block at the jth position of all file copies and its tag.

(9)IndiceRetri. The indices of corrupted data blocks can be identified by using this retrieval algorithm. The response $\left(T,\xi \right)$ generated by the CSP will be correct and will pass the third-party auditor's verification only if the data blocks in all copies are consistent and intact. Hence, there exist one or more corrupted data blocks; the whole verification procedure fails. When file copy is corrupted, the data owner should recover the file copy timely for ensuring that the authorized users in different locations can normally use the file copy. If the corrupted copy only includes one corrupted data block, updating the whole copy file may lead to huge computational and communication cost. Therefore, it is necessary to identify the indices of corrupted data block in corrupted file copy. We show a detailed retrieve algorithm in Algorithm 1.

Algorithm 1: Retrieve corrupted block index.

Input   $\left(T,\xi \right)$ and $k_{\mathrm{1}}$ , $k_{\mathrm{2}}$ , verify $e(T,g)\stackrel{?}{=}e\left({\prod }_{(j^{\prime },r_{j^{\prime }})\in S}{{\prod }_{i=\mathrm{1}}^{\tau }h\left(F_N‖i‖j^{\prime }\right)}^{r_{j^{\prime }}}\cdot u^{{\sum }_{i=\mathrm{1}}^{\tau }{\xi }_i},Y\right)$

 If the validation fails

 Then require the CSP to send ( ${\tilde{b}}_{ij},T_{ij}$ ) to the verifier

    the verifier computes the following τ verification equation:

    verify $\mathrm{\hspace{0.17em}\hspace{0.17em}}(\mathrm{1})e\left(T_{\mathrm{1}},g\right)\stackrel{?}{=}e\left({\prod }_{(j^{\prime },r_{j^{\prime }})\mathrm{\hspace{0.17em}\hspace{0.17em}}\in S}h{\left(F_N‖i\right)}^{r_{j^{\prime }}}\cdot {\omega }^{{\xi }_{\mathrm{1}}},Y\right)$

     $\cdots$

    and $(\tau )e\left(T_{\tau },g\right)\stackrel{?}{=}e\left({\prod }_{(j^{\prime },r_{j^{\prime }})\in S}h(F_N‖i{)}^{r_{j^{\prime }}}\cdot {\omega }^{{\xi }_{\tau }},Y\right)$

    where $T_t={\prod }_{(j^{\prime },\mathrm{\hspace{0.17em}\hspace{0.17em}}{r}_{j^{\prime }})\in S}{T}_{i{j}^{\prime }}^{r_{j^{\prime }}}$ ,

    If the validation $(t{)}_{\mathrm{1}\le t\le \tau }$ fails

    Then compute $n_{c_t}=⌈\sqrt{c_t}⌉$ and $n_{c_t}^{\prime }=⌊\sqrt{c_t}⌋$ , divide S into $n_{c_t}^{\prime }$ parts, $S_{{\mathrm{1}}_t},S_{{\mathrm{2}}_t},\dots ,S_{n_{c_t}^{\prime }}$

    where $S_{{\iota }_t},\left(\mathrm{1}\le \iota \le n_c^{\prime }\right)$ include $n_{c_t}$ elements, $S_{n_{c_t^{\prime }}}$ includes $c-n_{c_t}\cdot (n_{c_t}^{\prime }-\mathrm{1})$ ,

        $c_t$ denotes the number of data block which can not pass verification

    verify $({\mathrm{1}}_t)e\left(T_{1_t},g\right)\stackrel{?}{=}e\left({\prod }_{(j^{\prime },r_{j^{\prime }})\in S_{{\mathrm{1}}_t}}h(F_N‖i{)}^{r_{j^{\prime }}}\cdot {\omega }^{{\xi }_t^{{\mathrm{1}}_t}},Y\right)$

    and $\left(n_{c_t}^{\prime }\right)e\left(T_{n_{c_t}^{\prime }},g\right)\stackrel{?}{=}e\left({\prod }_{(j^{\prime },r_{j^{\prime }})\in S_{n_{c_t}^{\prime }}}h(F_N‖i{)}^{r_{j^{\prime }}}\cdot {\omega }^{{\xi }_t^{n_{c_t}^{\prime }}},Y\right)$

    Until   $n_{c_t}=\mathrm{2}$ or check all corrupted data block

    End

 End

End

The retrieve algorithm inputs four elements: T, ξ, $k_{\mathrm{1}}$ , and $k_{\mathrm{2}}$ . If CSP's response does not pass the verification, the third-party auditor uses Algorithm 1 to identify the index of corrupted data block. The third-party auditor first identified which cloud server contains the corrupted data copies. Then he/she checks out the damaged data copies from the cloud server which contains the damaged data copies. The verifier calculates $n_c=⌈\sqrt{c}⌉$ and $n_c^{\prime }=⌊\sqrt{c}⌋$ and divides S into $n_c^{\prime }$ parts, $S_{\mathrm{1}},S_{\mathrm{2}},\dots ,S_{n_c^{\prime }}$ , where $S_t\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le t\le n_c^{\prime }-\mathrm{1})$ includes $n_c$ elements and $S_{n_c^{\prime }}$ includes $c-n_c(n_c^{\prime }-\mathrm{1})$ elements. Then, the third-party auditor, respectively, verifies the correctness of data block whose index locates in $S_t$ . If the response can pass the third-party auditor's verification, the data blocks whose indices belong to $S_t$ will be kept correctly. Otherwise, the verifier will continue to check the integrity of smaller range data block (the number of data blocks $⌊\sqrt{c_t}⌋$ ) until remaining two data blocks or checking all corrupted data blocks. Finally, we can get the indices of corrupted data block in the cloud server. Thus, when the data owner recovers the corrupted copies, he/she only needs to regenerate a correct data block to replace the corrupted data block rather than regenerating a new file copy.

We give an example for Algorithm 1. As shown in Figure 4, Algorithm 1 first gets the corrupted data block copies ${\tilde{F}}_{\mathrm{2}}$ and ${\tilde{F}}_{\tau }$ which are marked with blue frame and then obtains the corrupted copies information ${\tilde{b}}_{i\mathrm{1}}$ and ${\tilde{b}}_{i\mathrm{3}}$ . That is, the actually corrupted data blocks are ${\tilde{b}}_{\mathrm{21}}$ and ${\tilde{b}}_{\tau \mathrm{3}}$ which are marked with red frame. Therefore, the data owner only needs to regenerate the data block copies ${\tilde{b}}_{\mathrm{21}}$ and ${\tilde{b}}_{\tau \mathrm{3}}$ and restores them in the copies ${\tilde{F}}_{\mathrm{2}}$ and ${\tilde{F}}_{\tau }$ , respectively.

Figure 4

Example of Algorithm 1.

4. Security Analysis

Theorem 1.

If both the data owner and the CSP are honest to perform the DPRDP scheme, the response of CSP can pass the auditor's validation:

$$\begin{array}{cc}& e\left(T,g\right)=e\left({{\displaystyle \prod }}_{\left(j^{\prime },r_{j^{\prime }}\right)\in S}\hspace{0.17em}{\displaystyle \prod }_{i=1}^{\tau }{T}_{i{j}^{\prime }}^{r_{j^{\prime }}},g\right)=e\left({{\displaystyle \prod }}_{\left(j^{\prime },r_{j^{\prime }}\right)\in S}\hspace{0.17em}{\displaystyle \prod }_{i=1}^{\tau }{\left(h\left(F_N‖i\right)·{\omega }^{{\tilde{b}}_{ij}}\right)}^{r_{j^{\prime }}},Y\right)=e\left({{\displaystyle \prod }}_{\left(j^{\prime },r_{j^{\prime }}\right)\in S}\hspace{0.17em}{\displaystyle \prod }_{i=1}^{\tau }h{\left(F_N‖i\right)}^{r_{j^{\prime }}}·{\omega }^{{\sum }_{i=1}^{\tau }{\xi }_i},Y\right).\end{array}$$

(5)

Theorem 1 is proved. The details of security analysis are given in the following.

(1) Scenario. In our protocol, there exist four entities in the security model: the data owner, verifier, CSP, and authorized user. The security analysis of protocol involves the first three participants, so we only consider the communication among the data owner, verifier, and CSP. The data owner encrypts data block and gets the replicas of each data block. Then the data owner generates the tags corresponding to the data block replicas and stores the block-tag pair on the CSP. When the verifier wants to validate the integrity of data copies, it sends to the CSP a challenge vector. Upon receiving the challenge vector, the CSP aggregates the tag of challenged data block and the challenged data blocks, respectively, and then sends the aggregation back to the verifier. That is, the verifier sends a challenge vector to the CSP, and then the CSP makes a response for the challenge. Finally, the verifier checks the aggregation information. The interaction among the data owner, CSP, and verifier is shown in Figure 5.

Figure 5

The interaction among the data owner, CSP, and verifier.

(2)Possible Attack

(a) Internal Attack. The main internal attack considered in our scheme refers to forgery attack, replacement attack, and replay attack. All these attacks initiated by dishonest CSP. The dishonest CSP may forge a single data block tag or replace a corrupted data block-tag pair with another valid block-tag pair. Even, he/she may also try to make a response to the current challenge of verifier with the previous proof, without querying the current data block actually.

(b) External Attack. An adversary may temper the messages transmitting on the channel.

(3)Interaction Protocol Design. In order to clearly present interaction between any two participants, a detailed communication process is given in Figure 6.

Figure 6

The communication process among the data owner, CSP, and verifier.

(4)Security Analysis

(a) External Attack. An adversary may temper the transmitted messages on channel shown in Figure 4. On the first transmission channel, the data owner sends $\left(T_{ij},{\tilde{b}}_{ij}\right)$ and tag $\mathrm{T}\mathrm{a}\mathrm{g}\left(T_{ij},{\tilde{b}}_{ij}\right)$ to the CSP. Upon receiving these elements, the CSP verifies whether the received block-tag pair $\left(T_{ij},{\tilde{b}}_{ij}\right)$ is correct or not according to $\mathrm{T}\mathrm{a}\mathrm{g}\left(T_{ij},{\tilde{b}}_{ij}\right)$ and the public key Y. If the adversary tempers $T_{ij}$ or ${\tilde{b}}_{ij}$ , the CSP would fail to validate and refuse to store the received $\left(T_{ij},{\tilde{b}}_{ij}\right)$ . Therefore, the adversary cannot attack successfully in the first channel.

For the adversary, tempering with the transmitted messages on the channels ② and ③ can be regarded as the CSP tempering with these messages. In addition to tempering messages, the CSP can also initiate forgery, replacement, and replay attack. That is, the CSP has stronger attack ability than an external adversary. Therefore, for the messages transmitted on the second and the third channel, we just need to consider the internal attack initiated by the CSP.

(b) Internal Attack

Forgery. A dishonest CSP attempts to forge the tag for some data block and wishes that the value of forged tag is the same as the original tag. For a single tag $T_{ij}={\left(h(F_N‖i)·{\omega }^{{\tilde{b}}_{ij}}\right)}^{\delta }$ , the CSP may change the input information of hash function $h(·)$ and the value of ${\tilde{b}}_{ij}$ . Because the hash function $h(·)$ resists collision, the hash result would change a lot if the CSP changes the input value of $F_N$ , i, or j. For the random element $\omega \in {\mathcal{G}}_1$ , the exponentiation result would change significantly if the CSP changes ${\tilde{b}}_{ij}$ . Therefore, it is hard for the CSP to forge a single tag.

Replacement. Assuming that the CSP uses a valid block-tag pair $(T_{iw},{\tilde{b}}_{iw}{)}_{w\notin S}$ to replace some block-tag pair $(T_{il},{\tilde{b}}_{il}{)}_{l\in S}$ . We get a conclusion that if the CSP replaces $(T_{il},{\tilde{b}}_{il}{)}_{l\in S}$ using another valid block-tag pair $(T_{iw},{\tilde{b}}_{iw})$ , the proof $(T^{\prime },{\xi }^{\prime })$ passes the third-party auditor's verification with negligible probability.

According the verification equation, the following equations are obtained:

$$\begin{array}{cc}& e\left(T^{\prime },g\right)=e\left({{\displaystyle \prod }}_{\left(j^{\prime },r_{j^{\prime }}\right)\in S,j^{\prime }\ne l}\left({{\displaystyle \prod }}_{i=1}^{\tau }h{\left(F_N‖i\right)}^{r_{j^{\prime }}}·{\omega }^{{\sum }_{i=1}^{\tau }{\sum }_{\left(j^{\prime },r_{j^{\prime }}\right)\in S,j^{\prime }\ne l}{r}_{j^{\prime }}·{\tilde{b}}_{i{j}^{\prime }}}\right)·\left({{\displaystyle \prod }}_{i=1}^{\tau }h{\left(F_N‖i\right)}^{r_w}·{\omega }^{{\sum }_{i=1}^{\tau }{r}_w·{\tilde{b}}_{iw}}\right),Y\right)\\ e\left(T,g\right)=e\left({{\displaystyle \prod }}_{\left(j^{\prime },r_{j^{\prime }}\right)\in S}\hspace{0.17em}{{\displaystyle \prod }}_{i=1}^{\tau }h{\left(F_N‖i\right)}^{r_{j^{\prime }}}·{\omega }^{{\sum }_{i=1}^{\tau }{\xi }_i},Y\right).\end{array}$$

(6)

We set

$$\begin{array}{cc}& {{\displaystyle \prod }}_{i=1}^{\tau }h{\left(F_N‖i\right)}^{r_w}·{\omega }^{{\sum }_{i=1}^{\tau }{r}_w·{\tilde{b}}_{iw}}=g^{x^{\prime }},\\ {{\displaystyle \prod }}_{i=1}^{\tau }h{\left(F_N‖i\right)}^{r_l}·{\omega }^{{\sum }_{i=1}^{\tau }{r}_l·{\tilde{b}}_{il}}=g^{y^{\prime }},\end{array}$$

(7)

where $x^{\prime },y^{\prime }\in {\mathcal{Z}}_q^{\ast }$ , $x^{\prime }\ne y^{\prime }$ .

If $(T^{\prime },{\xi }^{\prime })$ can pass the verifier's verification, we have $g^{x^{\prime }}=g^{y^{\prime }}$ . Since q is a large prime integer, the probability of $g^{x^{\prime }}=g^{y^{\prime }}$ is negligible.

Replay. The essence of replay attack is to use the previous proof to replace the current challenge's response. That is, the CSP does not actually access the latest data status. To some extent, the replay attack can be regarded as the multiple replacement attack. Therefore, we can use the same analysis method as replacement attack to analyze replay attack. If the challenged latest block-tag pairs are different with the previous block-tag pairs, the previous response will not pass the verifier verification.

5. Performance Analysis

In terms of our scheme implementation, we have simulated this MR-PDP protocol in C language. We conduct the following experiments on the Win7 system. To start, we perform several experiments on a system with an Intel(R) Core(TM) 3.10 GHZ processor and 4 GB RAM computer. We set the encryption security parameters $\lambda =\mathrm{60}$ according to [28]. We store copies of a data file of sizes 1 MB, 5 MB, 10 MB, and 20 MB, and their copies are divided into ${\mathrm{2}}^{\mathrm{18}}$ blocks. We assume that the elliptic curve group we deal with has a 256-bit group order [30]. The communication cost for each stage (file size 1 MB) in this protocol is presented in Table 1, where s is number of data files, $B_h$ is the size of hash function, C denotes the size of ciphertext, $B_N$ is the size of the file name, and $\Delta C$ is the size of $\mathrm{F}\mathrm{H}\mathrm{E}(\Delta b_j)$ .

Table 1

DPRDP scheme communication cost with file size 1 MB.

Phase	Cost	Data	From	To
Storage	${\mathrm{2}}^{\mathrm{23}}\cdot \log C$ bits	C	Data owner	CSP
Challenge	${\log }_{\mathrm{2}}n+\mathrm{2}{\log }_{\mathrm{2}}q$ bits	$$(c,k_1,k_2)$$	Data owner/verifier	CSP
Verification	$\tau \cdot c\cdot (\mathrm{2}\cdot q^{\mathrm{2}}\cdot B_h\cdot C\cdot \log q+\log C\cdot q)$ bits	$$\left(T,\xi \right)$$	CSP	Data owner/verifier
Update	$\log B_N+\log \mathrm{\Delta }C+\mathrm{2}\cdot \tau \cdot q\cdot B_h\cdot C\cdot \log q$ bits	$$(F_N,\mathrm{R}\mathrm{e}\mathrm{q}\mathrm{u}\mathrm{s}\mathrm{e}\mathrm{t},j,\text{FHE(}\mathrm{\Delta }{b}_j\text{)},T_{ij}^{\prime })$$	Data owner	CSP
Retrieval	$$c\cdot \tau \cdot (\mathrm{2}\cdot B_h\cdot C\cdot \log q+\log C)$$	$$(T_{ij},{\tilde{b}}_{ij})$$	CSP	Data owner/verifier

We give a performance comparison between the MR-PDP scheme proposed in our scheme and the DMR-PDP scheme proposed in [29].

Figure 7 presents the data setup computation time comparison between the DMR-PDP scheme and the DPRDP scheme using three copies for the file sizes 1, 5, 10, and 20 MB, respectively. Similarly with the scheme in [29], the data setup process is completed by the data owner only once. As shown in Figure 7, the DPRDP scheme performs faster than DMR-PDP scheme.

Figure 7

The Ccmparison of data setup time between DMR-PDP and DPRDP scheme.

We use the FHE encryption to generate the data block copy, but Raghul uses the Paillier encryption to generate the data block copies in DMR-PDP scheme. The following three elements are considered as the main influence factors for the efficiency of data setup. (1) The generation of encryption parameters: the time for generating parameter of FHE is much faster than that in Paillier encryption. In addition to generating random numbers, Paillier encryption also needs to compute the least common multiple which is a relatively consuming time process when both p and q are large number. However, this is not the main factor to affect the efficiency of data setup. (2) Encryption: the time complexity of FHE is $O(\gamma )$ and the time complexity of Paillier encryption is $2·O({\left(\mathrm{l}\mathrm{o}\mathrm{g}\hspace{0.17em}N\right)}^3)$ . Referring to the security parameter in DMR-PDP scheme and DPRDP, we get $O(\gamma )<2·O({\left(\mathrm{l}\mathrm{o}\mathrm{g}\hspace{0.17em}N\right)}^3)$ . The encryption time is the main factor of influencing the data setup efficiency. As shown in Figure 8, the computation difference between DMR-PDP scheme and DPRDP scheme is more and more obvious with the increase of file size. (3) Signature parameter setting: both DMR-PDP scheme and DPRDP scheme are involved in power computation. But the DMR-PDP scheme also needs to complete N times multiplication and addition operations; it will slow down the computation speed. Therefore, the data setup efficiency of the DPRDP scheme is better than that in the DMR-PDP scheme. In particular, when the file size increases, the advantage of the DPRDP scheme is more obvious.

Figure 8

(a) The comparison of data owner computation time for signatures between DMR-PDP and DPRDP scheme with file size of 1 MB and 5 MB. (b) The comparison of data owner computation time for signatures between DMR-PDP and DPRDP scheme with file size of 10 MB and 20 MB.

In Figure 8, the signing efficiency comparison of data owner in DPRDP scheme and DMR-PDPD scheme is presented. We set the number of replicas as 3, 5, and 10. The solid line denotes the signing time of data owner in DMR-PDP scheme and the dotted line represents the signing time of data owner in DPRDP scheme.

The signing efficiency comparison of data owner in DPRDP scheme and DMR-PDPD scheme for file sizes 1 MB and 5 MB is shown in Figure 8(a). The red line denotes the data owner signing time comparison with file size 1 MB for the number of copies 3, 5, and 10. Although the algorithms for generating tags in DPRDP scheme and DMR-PDP scheme are two similar methods, but multiplication and addition must be needed in DMR-PDP scheme, the signing time will be slower than that in DPRDP scheme. The blue line denotes the data owner signing time comparison with file size 5 MB for the number of copies 3, 5, and 10. When there exist 3 data copies, the signing time in DMR-PDP scheme is 0.037 seconds slower than that in DPRDP scheme. In Figure 8(b), we show the signing efficiency comparison of data owner in DPRDP scheme and DMR-PDPD scheme for file sizes 10 MB and 20 MB. The green line denotes the data owner signing time comparison with file size 10 MB with the number of copies 3, 5, and 10. When the file size is 10 MB, the difference of signing time between these two schemes is small. In Figure 8(b), the purple line denotes the data owner signing time comparison with file size 20 MB with the number of copies 3, 5, and 10. For 20 MB file, the growth rate of signing time in DMR-PDPD and DPRDP scheme increases a little when the number of copies changes from 3 to 5.

The tag aggregation efficiency comparison of CSP in DPRDP scheme and DMR-PDPD scheme is presented in Figure 9. Let the number of replicas be 3, 5, and 10. The solid line denotes the tag aggregation time of CSP in DMR-PDP scheme and the dotted line represents the tag aggregation time of CSP in DPRDP scheme.

Figure 9

(a) The comparison of CSP computation time for aggregation tag between DMR-PDP and DPRDP scheme with file size of 1 MB and 5 MB. (b) The comparison of CSP computation time for aggregation tag between DMR-PDP and DPRDP scheme with file size of 10 MB and 20 MB.

In Figure 9(a), we show the tag aggregation efficiency comparison of CSP in DPRDP scheme and DMR-PDPD scheme for file sizes 1 MB and 5 MB. The red line denotes the CSP aggregation time comparison with file size 1 MB for the number of copies 3, 5, and 10. For the algorithms for aggregation tags in DPRDP scheme and DMR-PDP scheme are two similar methods, the difference of aggregation time between these two schemes is small when the file size is 1 MB. The blue line denotes the CSP aggregation time comparison with file size 5 MB with the number of copies 3, 5, and 10. When there exist 3 data copies, the aggregation time in DMR-PDP scheme is 2.2 seconds slower than that in DPRDP scheme. The aggregation efficiency difference between DMR-PDP scheme and DPRDP scheme narrows as the increase of number of copies. When the number of copies is 10, the aggregation efficiency of the two schemes is very close.

The aggregation efficiency comparison of CSP in DPRDP scheme and DMR-PDPD scheme for file sizes 10 MB and 20 MB is shown in Figure 9(b). The green line denotes the CSP aggregation time comparison with file size 10 MB for the number of copies 3, 5, and 10. When the file size is 10 MB, the difference of aggregation time between these two schemes is small. With the increase of number of copies, growth rate of aggregation time is getting bigger. The purple line denotes the CSP aggregation time comparison with file size 20 MB for the number of copies 3, 5, and 10. Also, the growth rate of aggregation time is getting bigger for both DMR-PDP scheme and DPRDP scheme. For 20 MB file, the growth rate of aggregation time in DMR-PDPD scheme is faster than that in DPRDP scheme when the number of copies changes from 5 to 10. Therefore, when both the number of data copies and the file size are large, the DPRDP scheme is more effective.

6. Conclusion

In this paper, we have presented a dynamic replicated data possession checking scheme for checking the data copies integrity in the CSP. The data owners encrypt their data using FHE algorithm, obtain the data replicas, and then store their encryption data replicas on the CSP. Firstly, the proposed scheme not only supports checking integrity of the data file copies anytime and anywhere but also satisfies public verification without leaking any information to the third-party auditor. Secondly, the authorized users can decrypt data copies received from the CSP using a single decryption secret key. Thirdly, the data owner can implement data block update operation on data replicas. Finally, the retrieval algorithms in this scheme can identify the corrupted data blocks in corrupted copies accurately. The corrupted data block copies can be reconstructed by the data owner, and thus he/she needs not to generate the whole corrupted copy file. Through security analysis, we have shown that our scheme can resist forgery attacks, replacement attack, and replay attack. At the same time, our DPRDP scheme achieves a higher efficiency than DMR-PDP scheme.

We consider that there exists data expansion in the encryption process, so how to reduce the data expansion is our future work. Thus, we can further improve the efficiency of the proposed scheme.