P 3 DP: privacy preserving provable data possession with multi-copy and data dynamics in a cloud storage

Abstract

Nowadays, cloud storage has become an attractive storage scheme for a user to store his files. When a user stores his files on a remote cloud storage system, he cannot make sure whether his files are intact, so he must use some protocol to check the integrity of his files in the cloud storage. To guarantee high availability, some cloud storage servers provide a kind of highly-available service, which stores multiple copies of user files in the cloud storage, and the file owner cannot make sure whether all these copies are intact as well. Some cloud storage servers allow his users to operate their files online. As the file owner cannot always be online, he must entrust a trusted public data auditor to check his files in the cloud storage. In this work, we investigate the above issues about provable data possession with multi-copy and data dynamics supporting public verification in a cloud storage. We design a kind of authenticated 2-3 tree with ordered leaves and use this kind of tree to organize file block tags. We design a privacy preserving provable data possession scheme with multi-copy and data dynamics which supports public verification, and use a kind of RSA tag to construct this scheme. We apply our scheme to a cloud file backup system. Our theoretical proofs and experiments show that our scheme is feasible and reasonable.

Keywords

Cloud storage data dynamics multi-copy provable data possession privacy preserving

1 Introduction

1.1 Motivation

With the advancement of network technology, many users have outsourced their storage and computing needs [27]. Cloud storage becomes an attractive storage scheme for a user to store his files, which can reduce his maintenance cost, prevent his files from data corruption, and share his files with other persons. To satisfy the market demands, some cloud storage productions have been deployed in recent years, e.g., Amazon S3 [1] and Google Cloud Storage [17] are the two most prestigious cloud storage systems. All these cloud storage servers are deployed in some remote data centers, which are controlled, managed and maintained by some cloud storage providers. A file owner cannot physically possess his files, which raises some formidable and challenging tasks related to file security in a cloud storage. According to an investigation in [30], cloud storage security has become a lion in the way for large-scale application of cloud storage. It is important for a cloud storage provider to provide some file security mechanisms for its users. Generally speaking, file security consists of privacy, integrity and availability. A cloud storage provider can provide some encryption softwares based on some off-the-shelf encryption algorithms for a user to protect his file privacy. However, to resolve the file integrity problem, a cloud storage provider must provide his users with some file integrity checking tools. Up to now, researchers have designed two kinds of integrity checking scheme in the literature, namely, PDP [12, 13] and POR [3]. In POR, it inserts some tags as sentinels in a file, and uses a kind of erasure code to code this file. All sentinels are arranged in the file before being sent to an untrusted server, so it can be used to check the file only limited times. Subsequently, many researchers have extended these two kinds of schemes for different application fields with different properties, such as support public verification [8 , 42], data dynamics [5 , 42], privacy preservation [8], resource-constrained mobile devices [23] or cloud storage [19 , 51].

To guarantee file availability, we can store multiple copies of the file in multiple servers using replication technique. We refer to this kind of cloud storage as multi-copy cloud storage. Usually there exist two kinds of storage services which are highly-available service and ordinarily-available service in a multi-copy cloud storage. We can regard the ordinarily-available as a special case of highly-available service that we stores only one file copy in a cloud storage. If a user requires a highly-available storage service, cloud storage server will replicate the user’s files according to the service level and store all these copies in the cloud storage. Accordingly, the cloud storage providers charge the file owners according to his renting storage space and service level. The same file will be charged more when it is stored in a higher service level. As his files are stored in the cloud storage, the file owner cannot make sure whether there exist exact number of copies according to the service level, rather than store only one copy. To resolve this problem, Curtmola et al. [45] proposed a MR-PDP scheme. Hereafter, Barsoum et al. [2] brought forward a more efficient MR-PDP scheme. But, there are two shortcomings in their schemes. Firstly, all their schemes only check static file data, not supporting data dynamics. When a user wants to modify or delete some blocks of his files, he must download his files to his local computer, operate his files, regenerate all copies and retransmit these copies to the remote server. This will bring about tremendous overhead of network and computation. Secondly, their schemes don’t support public verification. A user must be online all the day and check these files by himself. If there are some lawsuits about file security between a cloud storage provider and a file user, there does not exist a public data auditor to arbitrate this affair fairly.

1.2 Our Contributions

To solve above problems, we design a provable data possession scheme with multi-copy and data dynamic in a cloud storage, which supports public verification. The contributions of this work can be summarized as follows.

Firstly, we propose a privacy preserving provable data possession scheme with multi-copy and data dynamics in a cloud storage. In the following section, we call it P³DP for short.

Secondly, we construct the P³DP with a kind of RSA tag, and apply it to a cloud file backup system.

Thirdly, we prove that the construction of P³DP is secure and efficient from theoretical perspective.

Fourthly, we conduct some experiments for the P³DP with a kind of RSA tag. Results of experiments show that P³DP is rational and feasible.

The paper is organized as follows: In Section 2, we describe and give some definitions about the problem. The authenticated 2-3 tree with ordered leaves is presented in Section 3. In Section 4, we introduce the privacy preserving provable data possession with multi-copy and data dynamics in a cloud storage and give a construction for the scheme with a kind of RSA tag. In Section 5, we give some rigorous proofs about security for the construction. In Section 6, we describe how P³DP can be applied to a cloud file backup system. Our implementation and experiment results are presented in Section 7. Finally, conclusions are given in Section 8.

2 The Problem and Definitions

2.1 The System Model

Our cloud storage system model is described in Fig. 1. It is made up of three different kinds of entities, a cloud storage provider, a file owner and a public data auditor (PDA). Each entity has different responsibility respectively. The file owner owns some files and stores them on the remote cloud storage servers owned by a cloud storage provider. The cloud storage provider stores multiple copies of the user’s files in his cloud storage servers. The file owner can entrust a PDA to check the integrity of his files in the cloud storage or do it by himself.

2.2 Problem Formalization

In this work, we study the problem of file integrity checking in a cloud storage, where there exist multiple copies for each file. The file owner can check the integrity of his files, and insert, delete, or modify his files remotely. If the file owner is not online, he can entrust a PDA to check the integrity of his files. We formalize the problem as follows: When a file owner decides to store a file F to a cloud storage, he generates m copies of F, we denote them as F_i (1 ≤ i ≤ m). No one can distinguish F_i from F_j (i ≠ j) and make sure whether all the F_i is generated by F except the file owner. Then the file owner generates a pair of public key and private key (p_k, s_k), keeps the s_k secret and makes the p_k public. It uses the private key and public key to generate φ_ij (1 ≤ j ≤ n) which are block tags of F_i, where n = len (F)/L and L is the length of file blocks. If the length of the last block does not equal to L, it will be padded with some random values. For simplification, we will use φ_i (1 ≤ i ≤ m) to denote all the tags of the F_i. Finally, the file owner sends all the F_i and φ_i to the cloud storage, and sends φ_i to the PDA. Hereafter, the file owner and PDA can audit the integrity of F_i. If some blocks of F_i are corrupted or deleted, PDA and file owner can detect it. If a PDA detects it, he will notify the file owner that some blocks are corrupted or deleted and the file owner will regenerate these blocks and sends them to the cloud storage. At the same time, the file owner can operate his files remotely, and the PDA can learn nothing about the inspected blocks in the audit process.

2.3 The Threat Model

From above discussion, we know that there are three threats in our file integrity checking scheme. Firstly, the cloud storage system provider only considers his economic benefits. He tries to delete some file blocks or preserves only one copy rather than m copies for his users to save his storage space, and the cloud storage system provider tries to use some kinds of skills to cheat the file owner or PDA that all these files are store correctly. Secondly, the cloud storage provider tries to get some information from all files stored in the cloud servers. Thirdly, PDA is a curious and honest adversary that tries to gain some knowledge from the audit process.

2.4 Some Notations

The security parameter throughout the paper is ν. We say that f (ν) is negligible if f (ν) = o (ν^-c) for every fixed constant c. We write negl (ν) to denote a negligible function. When saying that a Turing machine A is p . p . t. we mean that A is a uniform probabilistic polynomial time machine. We use i to denote file number, where 1 ≤ i ≤ m, and use j to denote block number, where 1 ≤ j ≤ n.

2.5 The P³DP Scheme

The P³DP scheme consists of five protocols which are initiation, data possession checking, file block requirement, dynamic operation and file block restoration.

(1) Initiation

The initiation protocol generates the system security parameters, block tags, file copies and a signature of the root of the tree that we use to organize block tags. It consists of Setup, GenTag, and GenCopy three algorithms.

Setup (ν) → {P_k, S_k, k, sgk, vk}. It is a probability algorithm which is run by the client. In the following sections, we use the client to denote the file owner. It takes the security parameter ν as input, and outputs a block encryption key k, a key pair (P_k, S_k), a signing key sgk and a verification key vk. S_k denotes the private key and P_k denotes the public key. The client keeps S_k and sgk secretly, and releases P_k and vk publicly.

GenCopy (F, m, k) → {F_i (i = 1, 2, …, m)}. This algorithm is run by the client. It takes the file F, replica number m and block encryption key k as input and outputs a set of copies F_i (i = 1, 2, …, m). All the F_i are different, without the block encryption key k, no adversary can use F_i to generate F_j where i ≠ j.

GenTag (F_i, S_k, sgk, g) → {φ_i, sig_sgk (H (R_i))}. This algorithm is run by the client. It takes the file F_i, private key S_k, signing key sgk and g as input and outputs a block tag set φ_i. F_i is an ordered collection of blocks {B_ij} and φ_i is a block tag set on {B_ij}. It also outputs sig_sgk (H (R_i)) which is the signature of R_i, where R_i is the root of the tree that we use to organize φ_i, and the leaves of the tree are hash values of B_ij.

(2) Data possession checking

Challenge (P_k, i) → {chal}. This algorithm is run by the client or PDA. It takes P_k and the copy id i as input and outputs the challenge chal for copy F_i.

GenProof (F_i, chal, φ_i) → {γ_i}. This algorithm is run by the server. It takes the challenge chal, file F_i, and file block tag set φ_i as input and outputs a data integrity proof γ_i for the blocks of the file F_i that specified by chal.

CheckProof (P_k, vk, chal, i, γ_i)→{success, failure}. This algorithm is run by the client or PDA. It takes the public key P_k, verification key vk, challenge chal, copy id i and the data integrity proof γ_i which is returned from the server as input. If the integrity of copy F_i is verified as correct, it outputs success, otherwise it outputs failure.

(3) File block requirement

GenBlockNo (i, j) → {bn}. This algorithm is run by the client. It takes i and j as input and outputs a block number bn for F_i.

TransmitBlock (F_i, bn, φ_i) → {B_ij, PF_ij}. This algorithm is run by the cloud server. It takes F_i, bn and φ_i as input and outputs B_ij. It also outputs PF_ij which is the proof of B_ij.

RestoreBlock (B_ij, PF_ij) → {success, failure}. This algorithm is run by the client. The client checks the proof of block B_ij, if it passes the proof checking, it decrypts B_ij using the block encryption key k and outputs success, otherwise it outputs failure.

(4) Dynamic operation

$Update (F_{i}, i, B_{ij}, T, φ_{i}) \to {F_{i}^{'}, φ_{i}^{'}, {sig}_{sgk} (H (R_{i}^{'}))}$ . This algorithm is run by the cloud server. T denotes the dynamic operation type. If T equals I, it denotes the insertion operation; if T equals M, it denotes the modification operation; if T equals D, it denotes the deletion operation. $R_{i}^{'}$ is the root of the tree to organize the block tags of $F_{i}^{'}$ , and ${sig}_{sgk} (H (R_{i}^{'}))$ is the signature of $R_{i}^{'}$ . Given F_i, i, B_ij, T, and φ_i, it outputs $F_{i}^{'}$ and $φ_{i}^{'}$ . It also outputs ${sig}_{sgk} (H (R_{i}^{'}))$ , which is obtained from the client.

(5) File block restoration

GenerateDuplicateBlock (i, k, j) → {B_ij}. This algorithm is run by the client. It first invokes the file block requirement protocol to get b_ij, then uses block encryption key k and i to generate the block B_ij, and sends B_ij to the cloud storage server.

Note that if one wants to restore F_i which has m blocks, it just invokes the File block restoration protocol m rounds.

2.6 Security Requirements

From above threat model, we can see that there are three security requirements in our P³DP. We refer to them as security against the cloud storage provider with public verifiability, privacy against the cloud storage provider and privacy against the public data auditor. In the following section, we will define these security requirements formally through some standard challenger-attacker attack games or simulation technique. In Game 1 and Game 2, we use the challenger to stand for either a file owner or a PDA, and use the adversary to stand for an untrusted cloud storage provider.

We first give a definition of security against the cloud storage provider with public verifiability using Game 1. In Game 1, a malicious adversary tries to delete some file blocks in its cloud storage to save storage space, and uses other block tags or other obtained information to generate a response R to pass the challenge for these deleted blocks. Game 1 has four phases: Setup, Query, Challenge and Forge.

Game 1.

Setup: The challenger runs the setup function of the P³DP, and gets (P_k, S_k). He sends P_k to the adversary and keeps S_k secret.

Query: The adversary adaptively selects some file blocks B_ij (i = 1, 2, ⋯ , m, j = 1, 2, ⋯ , n) and queries the verification tags from the challenger. The challenger computes verification tags φ_ij (i = 1, 2, ⋯ , m, j = 1, 2, ⋯ , n) for each of these blocks and sends φ_ij to the adversary, according to the protocol formulation.

Challenge: The challenger generates a challenge chal for the file block collection B_i = {B_i1, B_i2, ⋯ , B_in} of F_i and sends the challenge to the adversary.

Forge: The adversary computes a response R to prove the integrity of the requested file blocks of F_i using some forging blocks of F_i.

If Checkproof (P_k, B_i, chal, R, i) = success, then the adversary wins Game 1.

Definition 1 (Security against the cloud storage provider with public verifiability). If for any p . p . t . adversary, for all sufficiently large ν, the probability that the adversary wins the Game 1 on a collection of blocks of F_i satisfies (1),

\Pr [{win}_{Game 1} (ν)] < negl (ν)

(1)

then we say that the protocol is security against the cloud storage provider with public verifiability.

In Game 2, the malicious adversary try to play a game with challenger to distinguish a designated block from some random blocks in its cloud servers. If it can accomplish this task, then it can get some useful information from files that are stored in its cloud storage servers. Game 2 has five phases: Setup, Query1, Forge, Query2 and Guest. Game 2.

Setup: The challenger runs the setup function of the P³DP, and gets the public key and private key pair (P_k, S_k). It sends P_k to the adversary A and keeps S_k secret.

Query1: The adversary adaptively selects some file blocks B_ij of F_i, where i = 1, 2, ⋯ , m, j = 3, 4, ⋯ , n, and queries random values of these blocks from the challenger. The challenger generates some random values of these blocks and gives them to the adversary.

Forge: The adversary gives the challenger two file blocks B_i1 and B_i2 and the challenger selects j randomly, where j equals to 1 or 2, and sends the random value of B_ij to the adversary.

Query2: The adversary continues to query the file blocks except B_i1 and B_i2 as Query1.

Guest: The adversary guests j.

We say that the adversary wins Game 2 when the probability that the adversary guesses j correctly is more than 1/2.

Definition 2 (Privacy against the cloud storage provider). If for any p . p . t . adversary, for all sufficiently large ν, the probability that wins Game 2 on a collection of file blocks satisfies (2), $\Pr [{win}_{Game 2} (ν)] < \frac{1}{2} + negl (ν)$ (2) then we say that the protocol is privacy against the cloud storage provider. To define the privacy against the PDA, we decide to use the simulation technology in [37]. As the responsibility of PDA is to check data possession on behalf of a file owner, it tries to gain some knowledge from the audit process, we can regard it as a curious and honest adversary. If our protocol is zero knowledge [37], then the PDA cannot obtain any information from the protocol.

Definition 3 (Privacy against the PDA). If the PDA’s view is indistinguishable from the simulator’s output in the protocol’s execution, then we say that the protocol is privacy against the PDA.

3 An Authenticated 2-3 Tree with Ordered Leaves

To make our scheme efficient, we must use some data structure to organize block tags. Erway et al. designed a ranked skip list [6] and Wang et al. used an ordinary Merkle tree to support data dynamics [42]. As the efficiency of the ranked skip list is low and the depth of the ordinary Merkle tree is too large, which will affect the efficiency of tree operation, they cannot be applicable to our setting. In our multi-copy cloud storage, if there are n copies for F_i, there must exist n file block tag sets. If we use an ordinary Merkle tree to represent one block tag set, it will increase the cloud storage space and increase its search time. We must use some new data structure to organize file block tags. 2-3 tree is a kind of balanced tree that is proposed by Aho [4]. When blocks are modified, deleted or inserted, it should be more efficient in the hash 2-3 trees, as it has fewer depth than the one in a Merkle tree. As the hash 2-3 tree is a kind of searchable tree, it cannot be applicable to our setting directly. In order to support data dynamics and blockless verification efficiently, we design an authenticated 2-3 tree with ordered leaves.

Definition 4. An authenticated 2-3 tree with ordered leaves (A2-3OL tree) is a 2-3 tree with the difference that its leaves store the cryptographic hash values of file blocks, e.g. SHA-1 in practice (see Fig. 2). All the leaves are labeled with an ordered number from left to right, which is corresponding to the block number in the file, and its inner nodes store the hash values of their children nodes, which satisfies the following properties:

All the leaves in the tree have a sequence number.

Each interior node of the tree has two or three children.

Each path from the root to the leaf of the tree has the same length.

The root of the tree authenticates the entire tree.

There are three kinds of nodes in an A2-3OL tree (see Fig. 3), different types of nodes have different structures. A leaf node is composed of BN and H (B_BN), where BN stores block number and H (B_BN) stores hash value of B_BN. An inner node or a root node has six fields where first, second and third store a pointer that points its child respectively. If a node has two children then third will be null. If a node has one child then second and third will be null. H (W₁, W₂, W₃) is the hash value of its three children tags, if there is no third child then W₃ = R, where R denotes some random value. BN_low denotes the lowest block number of a leaf in its second subtree, and BN_high denotes the lowest block number of a leaf in the third subtree, and all block numbers of the first subtree are less than those in the second subtree and so does it between the second subtree and the third subtree.

4 A Construction for P³DP

We have defined P³DP in Section 2.5. In this section, we use a kind of RSA tag and A2-3OL tree to construct the P³DP.

(1) Initiation

$Setup (ν) \to {(g, N, e), d, k, \hat{x}, (\hat{p}, \hat{q}, \hat{g}, \hat{y})}$ . It takes the security parameter ν as input and outputs a block encryption key k, a public key P_k = (N, g, e), a secret key S_k = d, a signing key sgk = x and a verification key $vk = (\hat{p}, \hat{q}, \hat{g}, \hat{y})$ . ed = 1 mod (p - 1) (q - 1). N is a RSA modulus which is the product of p and q. All these quadratic residues modulo N form a multiplicative cyclic group QR_N where g is its generator. To make our scheme secure, we make p and q are two big prime numbers. As a general rule, we usually make p = 2p′ + 1 and q = 2q′ + 1 where p′ and q′ are also two big prime numbers. In our construction, we use DSA [39] to sign the root of A2-3OL tree.

GenCopy (F, m, k) → {F_i (i = 1, 2, …, m)}. It takes F, m and k as input and outputs a set of copies F_i (i = 1, 2, …, m). F_i is created by concatenating i behind each block of file F and encrypting them with AES. B_ij = E_k (B_ji) _{1≤i≤m,1≤j≤n}. The client keeps the secret key k to decrypt each copy block in the later time to restore the original blocks of file F. As k was kept by the file owner secretly, no one other than the file owner can restore F. It is widely believed that modern block ciphers, such as AES, have the avalanche property that a small change to its input will result in a large change to the output. So F_i and F_j (i ≠ j) are different.

GenTag (F_i, d, sgk, g) → {{T_i1, T_i2, ⋯ , T_in} , Sig_sgk (H (R_i))}. It takes F_i, d, sgk and g as input and outputs a set of verification tags φ_i = {T_i1, T_i2, ⋯ , T_in} (1 ≤ i ≤ m) and a root signature Sig_sgk (H (R_i)). It sends Sig_sgk (H (R_i)) to PDA and sends φ_i to the server. Sig_sgk (H (R_i)) is the signature of R_i which is the root of the A2-3OL tree of the file F_i. T_ij is a function of the tagged block B_ij which can be used by the server to prove possession of the corresponding block B_ij of F_i. T_ij = (g^B
_ij)^d mod N for 1 ≤ j ≤ n.

(2) Data possession checking

Challenge ((g, N, e) , i) → {i, k₁, k₂, g_s, c}. In order to check whether all blocks of the ith copy F_i are possessed in cloud servers exactly, the client or PDA challenges cloud servers to prove possession of a random subset blocks of file F_i. The challenge is made up of c, i, k₁, k₂ and g_s. k₁, k₂ and s are chosen randomly for each challenge. c is the number of challenged blocks and i denotes the ith copy of F. k₁ is a key for pseudorandom permutation Π₁ to determine the indexes of challenged blocks. k₂ is a key for the pseudorandom permutation Π₂ to determine some random numbers. g_s = g^s mod N, where $s \in Z_{N}^{*}$ .

GenProof (F_i, (i, k₁, k₂, g_s, c) , φ) → {p, T, {H (B_ij) , ω_j} _j∈J, Sig_sgk (H (R_i))}. After it receives a challenge from the client, the server uses a pseudorandom permutation Π₁ keyed with k₁ to determine j_t which is the indexes of challenged blocks of F_i, where j_t = Π₁k₁ (t) (1 ≤ t ≤ c), and uses the pseudorandom permutation Π₂ keyed with k₂ to generate the pseudorandom coefficient a_j, where a_j = Π₂k₂ (j) (1 ≤ j ≤ c). Then the server generates a proof of possession PR = (p, T, {H (B_ij) , ω_j} _j∈J, Sig_sgk (H (R_i))) for these blocks and returns PR to the challenger. p is computed by raising g_s to the sum of product of the challenged blocks and pseudorandom coefficient. $p = g_{s}^{(a_{1} B_{{ij}_{1}} + a_{2} B_{{ij}_{2}} + \dots + a_{c} B_{{ij}_{c}})} \mod N$ , and T is computed by multiplying the verification tags a_i power (1 ≤ j ≤ c) corresponding to the challenged blocks. T = (T_j
₁)^a
₁× (T_j
₂)^a
₂× ⋯ × (T_{j
_c})^a
_c. {ω_j} _j∈J are the node siblings on the path from the leaves {H (B_ij)} _j∈J to the root R_i of the A2-3OL tree. The server responds to the verifier with PR = (p, T, {H (B_ij) , ω_j} _j∈J, Sig_sgk (H (R_i))). R_i is the root of the A2-3OL tree of F_i and Sig_sgk (H (R_i)) is the signature of R_i.

CheckProof ((g, N, e) , vk, (i, k₁, k₂, g_s, c) , (p, T, {H (B_ij) , ω_j} _j∈J, Sig_sgk (H (R_i)) , H (R_i)) , s)→ {success, failure}. The client or PDA uses vk to check Sig_sgk (H (R_i)). If this check fails, it halts and outputs failure, otherwise it generates the root $R_{i}^{'}$ using {H (B_ij) , ω_j} _j∈J, and checks $(H (R_{i}^{'}))$ whether equals (H (R_i)). If this check fails, it halts and outputs failure, otherwise it checks if (T^e)^s equals p. If (T^e)^s equals p, it outputs success, otherwise it outputs failure.

(3) File block requirement

GenBlockNo (i, j) → {bn}. When the file owner requires the block j of F_i, it generates a block number bn = (i, j), and sends bn to the server.

TransmitBlock (F_i, bn) → {B_ij, {H (B_ij) , ω_ij} _j∈J, Sig_sgk (H (R_i))}. Once the file server receives bn, it sends the B_ij, {H (B_ij), ω_ij} _j∈J and Sig_sgk (H (R_i)) to the file owner.

RestoreBlock (B_ij, {H (B_ij) , ω_ij} _j∈J, Sig_sgk (H (R_i))} , k, vk) → {success, failure}. When the file owner receives B_ij, {H (B_ij) , ω_ij} _j∈J and Sig_sgk (H (R_i)), he uses vk to check Sig_sgk (H (R_i)). If this check fails, the file owner rejects it by outputting failure, otherwise he generates the root $R_{i}^{'}$ of the A2-3OL tree of F_i, and checks if $(H (R_{i}^{'}))$ equals (H (R_i)). If this check fails, the file owner rejects it by outputting failure, otherwise he decrypts the block using the privacy key k to restore B_ij and outputs success.

(4) Dynamic operation

$Update (F_{i}, i, B_{ij}, φ_{i}, T) \to {F_{i}^{'}, φ_{i}^{'}, {Sig}_{sgk} (H (R_{i}^{'}))}$ . T denotes the dynamic operation type. If T equals I, it denotes insertion operation; if T equals M, it denotes modification operation; if T equals D, it denotes deletion operation. $R_{i}^{'}$ is the root of the A2-3OL tree of $F_{i}^{'}$ and ${Sig}_{sgk} (H (R_{i}^{'}))$ is the signature of $R_{i}^{'}$ . Given F_i, i, B_j, φ_i and T, it outputs $F_{i}^{'}$ and $φ_{i}^{'}$ . It also outputs ${Sig}_{sgk} (H (R_{i}^{'}))$ , which is obtained from the file owner.

(5) File block restoration

GenerateDuplicateBlock (i, k, j) → {B_ij}. It first invokes the file block requirement protocol to get b_ij, then uses the block encryption key k and i to generate the block B_ij, and sends B_ij to the cloud storage server.

Note that if one wants to restore the entire file, which has m blocks, it just invokes the file block restoration protocol m rounds.

5 Security Analysis

Let N = pq be an RSA modulus where p = 2p′ + 1 and q = 2q′ + 1 are safe primes, QR_N is the unique cyclic subgroup of $Z_{N}^{*}$ where g is its generator. In this section, we will analyze the security of our construction of P³DP, and prove that it satisfies these security requirements that have been defined in Section 2.6.

Definition 5 (Factoring assumption). For any p.p.t adversary A, when given N, the probability that A can output p or q is negligible in the size of p and q.

Definition 6 KEA1-r (Knowledge of exponent assumption [32]). For any adversary A that given (N, g, g^s), where $s \leftarrow^{R} Z_{N}^{*}$ , as input and returns group elements (C, Y) such that Y = C^s, there exists an extractor $\hat{A}$ which, given the same inputs as A, returns x such that g^x= C.

Theorem 1. Under KEA1-r, factoring assumption and the signature is secure, our construction of the P³DP achieves security against the cloud storage provider with public verifiability under Definition 1.

Proof. The goal of the malicious cloud storage provider is to generate a proof that is not correctly computed from F_i, to pass the data possession checking of F_i. According to P³DP, we know that file blocks of F_i are created by concatenating i behind each file block of F and are encrypted with AES. It is infeasible for a cloud storage provider to employ blocks from other copy F_j (i ≠ j) to pass the data possession checking, even though the file owner uses the same secret key k to generate F_j. The provider must use other tricks to cheat the file owner or PDA in the data possession checking protocol.We use A to represent a malicious cloud storage provider and use B to represent a file owner or PDA. B plays Game 1 with A to simulate the data possession checking protocol for the copy F_i as the following steps:

B generates s, g, e, g_s and N, and gives (g, g_s, N) to A. g is the generator of QR_N, g_s = g^smod N.

A adaptively selects some file blocks B_ij (i = 1, 2, ⋯ , m, j = 1, 2, ⋯ , n) and queries the verification bock tags T_ij from B. B computes T_ij = (g^B
_ij)^dmod N, and gives T_ij to A.

B generates a chal = (i, c, k₁, k₂, g_s) for B_i which is the block collection of F_i, and sends chal to A.

A computes a response R = (p, T, {H (B_ij) , ω_j} _j∈J, Sig_sgk (H (R_i))) to prove data possession of these requested file blocks, where p, T, j_t and a_j satisfy following equations: $p = g_{s}^{(a_{1} B_{{ij}_{1}} + a_{2} B_{{ij}_{2}} + \dots + a_{c} B_{{ij}_{c}})} \mod N$ (3) $T = (T_{j_{1}})^{a_{1}} \times \dots \times (T_{j_{c}})^{a_{c}} \mod N$ (4) $j_{t} = Π_{1 k_{1}} (t) (1 \leq j \leq c)$ (5) $a_{j} = Π_{2 k_{2}} (j) (1 \leq j \leq c)$ (6)Π₁ and Π₂ are two pseudorandom permutations. Sig_sgk (H (R_i)) is the signature of the hash value of the root R_i of the A2-3OLtree.

If checkproof (e, chal, R) = success, then adversary A wins Game 1.We use pr [Win_A,Game1 (ν)] to denote the probability that A wins Game 1. A inputs (N, g, g^s) and outputs p,T,{H (B_ij) , ω_j} _j∈J and Sig_sgk (H (R_i))). As the signature is secure, we know that A cannot use some incorrect value of {H (B_ij) , ω_j} _j∈J and Sig_sgk (H (R_i)) to pass the data possession checking protocol. According to Equation (3) and Equation (4), we can get P = T^s as follows:

$\begin{matrix} p = g_{s}^{(a_{1} B_{{ij}_{1}} + \dots + a_{c} B_{{ij}_{c}})} \mod N \\ = (g^{(a_{1} B_{{ij}_{1}} + \dots + a_{c} B_{{ij}_{c}})})^{s} \mod N \\ = ((T_{j_{1}})^{a_{1}} \times (T_{j_{2}})^{a_{2}} \times \dots \times (T_{j_{c}})^{a_{c}})^{s} \mod N \\ = T^{s} \end{matrix}$ According to the KEA1-r assumption B can construct an extractor $\tilde{A}$ . When given the same input as A, it outputs x that satisfies Equation (7): $P = g^{x} \mod N$ (7) As P satisfies (3), B can compute x as Equation (8): $x = (a_{1} B_{{ij}_{1}} + a_{2} B_{{ij}_{2}} + \dots + a_{c} B_{{ij}_{c}})$ (8) In Equation (8), we have c unknowns. If B gets $\hat{c} (\hat{c} \geq c)$ verifying linearly independent equations on the same blocks, then B can solve each individual block B_ik, where k = j₁, j₂, ⋯ , j_c (1 ≤ i ≤ m). According to Game 1, we know that the goal of adversary A is to generate a proof that is not correctly computed from F_i to pass the data possession checking of F_i. So if adversary A wins Game 1, then B cannot get $\hat{c}$ verifying linearly independent equations on the same block, and we can construct $\tilde{B}$ to factor N as the following steps:

B passes x and tags in the previous proof to $\tilde{B}$ , along with the chal.

$\tilde{B}$ first checks to see if there is any tag mismatch: T_ij ≠ g^B
_ij mod N. For some 1 ≤ j ≤ c, B_ij are the original blocks. If this is the case, $\tilde{B}$ can output T_ij and g^B
_ij mod N for particular j as a collision.

If all the tags match these original blocks, $\tilde{B}$ uses the challenge and ids of these challenged blocks to compute linear combination d = (a₁B_ij
₁ + a₂B_ij
₂ + ⋯ + a_cB_{ij
_c}) of the original blocks. From the previous proof, we know T = g^x mod N. Since all the tags are matched, we have T_ij = g^B
_ij mod N, and we obtain T = g^d mod N where x ≠ d.

Using miller’s lemma [16], $\tilde{B}$ can factor N.

We use pr [FactorN] to denote the probability that

\tilde{B}

can factor N. But according to the factoring assumption, we can see that

\tilde{B}

can’t factor N. Therefore we can gets

$\Pr [{Win}_{A, Game 1} (ν)] = \Pr [FactorN] < negl (ν)$ This completes the proof of the theorem.□

Theorem 2. If AES is secure, our construction of the P³DP achieves privacy against the cloud storage provider under Definition 2.

Proof. We prove this theorem by the reduction argument. We assume that there exists a p.p.t. adversary A that wins Game 2, and we use $\hat{B}$ to denote the challenger in Game 2. We use Pr [Win_A,Game2 (ν)] to denote the probability that A wins Game 2, and define e (n) as Equation (9): $e (n) = Pr [{Win}_{A, Game 2} (1^{n})] - \frac{1}{2}$ (9) According to (9), we know that if A wins Game 2, then e (n) >0, and we can construct the following adversary $\tilde{A}$ that attacks the AES:

$\tilde{A}$ invokes $\hat{B}$ to run the setup function. $\hat{B}$ keeps k secret and gives ((g, N, e) , (d)) to $\tilde{A}$ . $\tilde{A}$ gives (g, N, e) to the adversary A.

$\tilde{A}$ firstly constructs an empty file block list for F_i. The list is consisted of two columns. The first column is used to store the file block and the second column is used to store its corresponding random value.

When gives some file blocks B_ij (j = 1, 2, ⋯ , n) of F_i to $\tilde{A}$ , $\tilde{A}$ will firstly check its file block list. If the file block is not in its file block list, $\tilde{A}$ will query $\hat{B}$ to get a random value and give this random value to A, then appends the file block and its corresponding random value in the file block list. If this file block is in the file block list, $\tilde{A}$ will return its corresponding random value in the list to the A.

A gives two file blocks B_i1 and B_i2 to $\tilde{A}$ . $\tilde{A}$ selects j1 randomly and sends to $\hat{B}$ . $\hat{B}$ sends AES_k (B_ij1) to $\tilde{A}$ . $\tilde{A}$ sends AES_k (B_ij1) to A and invokes A.

If A outputs the value j2 that equals j1 then $\tilde{A}$ outputs 1, otherwise $\tilde{A}$ outputs 0.

From the construction of adversary

\tilde{A}

, if the runtime of A is polynomial time, then the runtime of

\tilde{A}

is also polynomial time. The probability that adversary

\tilde{A}

attacks AES can be computed asfollows:

$\begin{matrix} \tilde{e} (n) = \Pr [{attack}_{aes, \tilde{A}} (1^{n})] \\ = \Pr [{Win}_{A, Game 2} (1^{n})] \\ = \frac{1}{2} + e (n) \end{matrix}$

If A wins Game 2 then $Pr [{attack}_{aes, \tilde{A}} (1^{n})] > 1 / 2$ . That means $\tilde{A}$ can attack AES successfully. But as we know that AES is secure, A cannot win Game 2. This completes the proof.□

Theorem 3. If AES is secure, our construction of the P³DP achieves privacy against the PDA under Definition 3.

Proof. We prove Theorem 3 by constructing a simulator for PDA, and prove that its output is computationally indistinguishable from PDA’s view. The simulator is given the same input of PDA. The PDA’s input is {N, g, {T_j} _j=1,2,⋯,n, {H (B_ij) , ω_j} _j∈J, Sig_sgk (H (R_i)) , k₁, k₂, s}, the PDA’s output is a bit o to indicate whether the checkproof function outputs success or failure. According to our P³DP, we can see that B_ij is the output of AES, and we can regard H (B_ij) and ω_j as some pseudorandom random values. Sig_sgk (H (R_i)) is public available to anyone, and as the server is honest, o is always 1. We construct the simulator $\tilde{S}$ as follows:

$\tilde{S}$ selects one random number s′.

$\tilde{S}$ randomly selects some numbers {j₁, j₂, ⋯, j_c} and some coefficient numbers {a₁, a₂, ⋯, a_c}.

$\tilde{S}$ sends a challenge (k, {j₁, j₂, ⋯ , j_c} , g^s′, {a₁, a₂, ⋯ , a_c}) to the server, and gets the output o.

Using the knowledge of {T_ij}(j = 1, 2, ⋯, n) $\tilde{S}$ computes T = ((T_ij
₁)^a
₁× (T_ij
₂)^a
₂× ⋯ × (T_{ij
_c})^a
_c mod N, p′ = (T^e)^s mod N, and PR′ = (p′, T, {H (B_ij) , ω_j} _j∈J, Sig_sgk (H (R_i)).

$\tilde{S}$ outputs (x, PR′). x denotes the PDA’s input where x = {N, g, {T_ij} _j=1,2,⋯,n, k₁, k₂, s}.

We use View_PDA to denote the PDA’s view during the execution of the protocol:

$\begin{matrix} {View}_{PDA} = (x, g_{s}^{(a_{1} B_{{ij}_{1}} + a_{2} B_{{ij}_{2}} + \dots + a_{c} B_{{ij}_{c}})} \mod N, \\ T, H (B_{ij}), ω_{j}}_{j \in J}, {Sig}_{sgk} (R_{i})) \end{matrix}$

T_ij (j = 1, 2, ⋯ , n) are the block tags which are available to anyone that are also included in the PDA’s view. In the simulator’s output (x, PR′) and the PDA’s view View_PDA, s and s′ are identical distribution and the other values are identical, so the simulator’s output and the PDA’s view are identical distribution, which are computationally indistinguishable. Therefore, PDA cannot get any information about the file in the course of data possession checking. This completes the proof.□

6 Using P³DP in cloud file backup application

In this section, we explain how to use P³DP in a cloud file backup system. As mentioned in the introduction, P³DP allows storing multiple copies of a file in the remote server, which are in the encrypted form. The file backup client software does not need to be modified much. Since all copies can be verified by the client in the encrypted form, using P³DP would provide stronger security and availability guarantee.Setup. Using P³DP in a file backup require the following setup:

A trusted client-side application that use P³DP client to setup the security parameter and replica number m (e.g. m = 2).

The file backup server software need to be modified to implement the GenProof and TransmitBlock of P³DP.

The client application maintains separate P³DP client state (e.g., block encryption key) for every backup file. All P³DP algorithms are described in Section 4.

Backup a file. To backup a file f to the cloud, the backup client application first uses P³DP.GenCopy to obtain m copies (f₁, f₂, …, f_m), then uses P³DP.GenTag to obtain file tags and the signature of A2-3OL tree root for each copy. At the same time P³DP.GenTag sends all these copies, file tags and signatures to the server, and the server stores these correctly. Restore a file. To restore a file f from the cloud, the backup client application first generates the block number of f and uses P³DP.GenBblockNo to generate blockNo for the P³DP.TransmitBlock in the server, then uses P³DP.RestoreBlock to restore all blocks in f. Check file backups. To check backups of f in the cloud, the backup client application first uses P³DP.Challenge, then uses P³DP.CheckProof to check the responses that are generated by P³DP.GenProof in the cloud server. If it returns success then backups of f are kept in good condition, otherwise, backups of f have beendestroyed.

7 Performance

7.1 Implementation

In order to demonstrate the feasibility of P³DP, we implemented it in C over the OpenSSL cryptographic library(version 0.98g) [38]. All algorithms in our implementation are described in Section 4. The cryptographic primitives for our implementation use OpenSSL. Encryption for the file block is the OpenSSL of 128-bit AES-CBC [47], and the hash function is the OpenSSL of SHA-256 [11]. The RSA for the block tag is the OpenSSL of RSA-1024 [46], and the signature of the root of A2-3OL tree is the OpenSSL of DSA [39].System actions (e.g. filesystem access and network transmission) and cryptographic computations are two kinds of time-intensive operations in the implementation of P³DP. As the systems costs will vary between underlying systems, to evaluate P³DP fairly, we don’t consider the system costs in our test framework; all operations are performed inmemory.

7.2 Experiments

All experiments were performed in Fedora 8.0 with kernel 2.6.23.1. The CPU of the experiment machine is Intel^® Pentium^® Dual E2160 1.8G and the RAM is 4GB. All experiments ran single-threaded on the processors. The Disk of the machine is Western Digital Caviar SE Hard Drive that has 320GB capacity, 7200rpm with 8 MB Cache. In the following experiments, the file size is 4MB, block size is 4KB, the number of each challenge is 460, and all data represents the mean of 10 trials.

We first study the scalability of P³DP when we create multiple copies and compare its performance to that of MR-PDP [45] and EMC-PDP [2]. The experiment results are shown in Fig. 4. The x axis represents the copy number, and the y axis represents the copy generation time. The copy generation time of the three schemes is almost equivalent. When the number of copy is less than or equal to 8, the copy generation time is less than 0.26 second. The copy generation time increases quickly when the number of copy increases, and it increases to about 2.5 second. So we can choose 8 as the ideal copy number.

Since the data possession checking is one of key functions of our P³DP, we evaluated the performance of P³DP in the data possession checking. This challenges in these experiments represent 99% confidence that less than 1% of the data have been damaged [12]. Ateniese et al. have demonstrated that if the server misses a portion of a file, then the number of blocks that the challenger needs to check, so as to detect the misbehavior of the server with a certain probability, is a constant amount of blocks, independently of the total number of file blocks: e.g., if the server misses 1% of the file F_i, then the challenger only wants to request proof of possession for 460 randomly chosen blocks of F_i which detects server misbehavior at least 99% [12]. Figures 5 and 6 show the processing costs of the server and client respectively, when the client challenges 460 blocks to the server for the different number of copies. The x axis in Figures 5 and 6 represents the number of copies to be checked in the experiments, the y axis in Fig. 5 represents the computation time spent by server, and the y axis in Fig. 6 represents the computation time spent by client. From these figures, we can see that computation time increased with the copy number in the server and client, our P³DP scheme outperforms EMC-PDP and MR-PDP, it reduces the server computation time when a large number of verifiers are connected to the server causing a huge computation overhead over the server, it also reduces the verifier computation time.

As there is no multi-copy PDP that supports data dynamics in the literature, we do the experiment of our P³DP against the DPDP-Skiplist [6] which uses an authenticated skip list to organize their tags and DPOR-Merkle [42] which uses a Merkle tree to organize their tags. To compare the performance of these scheme fairly in this experiment, we use our P³DP as a single DPDP and compare their insertion, deletion and modification time in server when the verifier wants to insert, delete or modify some blocks in the server. From Figs. 7–9 we can see that the server insertion performance outperforms those of the other schemes, while the deletion and the modification performances of our P³DP scheme are slightly slower than those of the other schemes. The reason is that the authenticated 2-3 tree is a kind of balanced tree. When we use it to organize the block tags, its tree depth is smaller than those of the authenticated skip list and the merkle tree. When the server inserts a block, it can quickly locate its insertion location. When the server delete or modify a block, it will cause the authenticated 2-3 tree to invoke the tree balance operation, which will add its deletion or modification operation time, while the other two data structures need not this tree balance operation. If we use the stochastic scheduling technology [28] and the batch processing technology [29] for block deletion or block modification in the server, then the server can reduce the number of tree balance operation at all, and it will improve the efficiency of block deletion or block modification eventually.

8 Conclusions

Cloud storage has become an important storage scheme for a user to store his files, but this scheme makes the file owner not possess his files physically, and raises some issues related to file security. In this work we have studied the problem of creating multiple copies of a file over the cloud servers and auditing all these copies to verify their correctness and completeness. We have proposed a privacy preserving provable data possession with multi-copy and data dynamics (P³DP) to achieve our goals, and have used a kind of authenticated 2-3 tree with ordered leaves and a kind of RSA tag to construct our P³DP. The security analysis and experimental results have showed that our construction of the proposed scheme is proven secure. As Hadoop is the prevailing cloud system [43], we will integrate P³DP to Hadoop in the future work.

Footnotes

Acknowledgments

The research was partially funded by the Key Program of National Natural Science Foundation of China (Grant Nos. 61133005, 61432005), and the National Natural Science Foundation of China (Grant Nos. 61370095, 61472124, 61502163).

References

Amazon simple storage service (Amazon S3), http://aws.amazon.com/s3/.

Barsoum

A.F.

and Hasan

M.A.

, Provable possession and replication of data over cloud servers, Centre For Applied Cryptographic Research (CACR), University of Waterloo, Report, vol. 32, 2010.

Juels

and Kaliski

, PORs: Proofs of retrievability for large files, In Proceedings of 14th ACM conference on Computer and communications security (CCS ’07), ACM Press, New York, 2007, pp. 584–597.

Aho

A.V.

, Ullman

J.D.

and Hopcroft

J.E.

, Data structures and algorithms, Addison-Wesley Longman Publishing Co., Inc, 1983.

Chen

and Curtmola

, Robust dynamic provable data possession, In Proceedings of 32nd International Conference on Distributed Computing Systems Workshops (ICDCSW), IEEE, New York, 2012, pp. 15–525.

Erway

, Kupcu

, Papamanthou

and Tamassia

, Dynamic provable data possession, In Proceedings of 16th ACM Conference on Computer and Communications Security (CCS ’09), ACM Press, New York, 2009, pp. 213–222.

Liu

, Li

, Xu

and Li

, Strategy configurations of multiple users competition for cloud service reservation, IEEE Transactions on Parallel and Distributed Systems27(2) (2016)508–520.

Wang

, Chow

S.M.

, Wang

, Ren

and Lou

W.J.

, Privacy-preserving public auditing for secure cloud storage, IEEE Transactions on Computers62(2) (2013)362–375.

Boneh

, Lynn

and Shacham

, Short signatures from the weil pairing, J Cryptology17(4) (2004)298–319.

10.

Stefanov

, Dijk

M.V.

, Juels

and Oprea

, Iris: A scalable cloud file system with efficient integrity checks, In Proceedings of the 28th Annual Computer Security Applications Conference, ACSAC’12, ACM Press, New York, 2012, pp. 229–238.

11.

FIPS 180-3, Secure Hash Standard (SHS), Federal Information Processing Standard (FIPS), Publication 180-3, National Institute of Standards and Technology, Washington, DC, 2008.

12.

Ateniese

, Burns

, Curtmola

, Herring

, Kissner

, Peterson

, Song

, Provable data possession at untrusted stores, In Proceedings of 14th ACM conference on Computer and communications security (CCS ’07), ACM Press, New York, 2007, pp. 598–609.

13.

Ateniese

, Burns

, Curtmola

, Herring

, Khan

, Kissner

, Peterson

and Song

, Remote data checking using provable data possession, ACM Transactions on Information and System Security14(1) (2011)1–34.

14.

Ateniese

, Pietro

R.D.

, Mancini

and Tsudik

, Scalable and efficient provable data possession, In Proceeding of 4th international conference on Security and privacy in communication networks(Secure Comm ’08), ACM Press, New York, 2008, pp. 1–10.

15.

Ateniese

, Kamara

and Katz

, Proofs of storage from homomorphic identification protocols, In Advances in Cryptology-ASIACRYPT 2009, Lecture Notes in Computer Science, Springer, 2009, pp. 319–333.

16.

Miller

G.L.

, Riemann’s hypothesis and tests for primality, JC-SS13(3) (1976)300–317.

17.

Google Cloud Platform, https://cloud.google.com/storage/.

18.

Shacham

and Waters

, Compact proofs of retrievability, J Cryptology26(3) (2013)442–483.

19.

Wang

, Proxy provable data possession in public clouds, IEEE Transactions on Services Computing6(4) (2013)551–559.

20.

Wang

and Zhang

, On the knowledge soundness of a cooperative provable data possession scheme in multicloud storage, IEEE Transactions on Parallel and Distributed Systems25(1) (2014)264–267.

21.

Mei

, Li

, Ouyang

and Li

, A profit maximization scheme with guaranteed quality of service in cloud computing, IEEE Transactions on Computers64(11) (2015)3064–3078.

22.

Stanek

, Sorniotti

, Androulaki

and Kencl

, A secure data deduplication scheme for cloud storage, In Financial Cryptography and Data Security, Springer, 2014, pp. 99–118.

23.

Yang

, Wang

, Tan

and Yu

, Provable data possession of resource-constrained mobile devices in cloud computing, Journal of networks6(7) (2011)1033–1040.

24.

Chen

, Using algebraic signatures to check data possession in cloud storage, Future Generation Computer Systems29(7) (2013)1709–1715.

25.

Bowers

K.D.

, Juels

and Oprea

, HAIL: A high-availability and integrity layer for cloud storage, In Proceedings of 16th ACM conference on Computer and communications security (CCS ’09), ACM Press, New York, 2009, pp. 187–198.

26.

Bowers

K.D.

, Juels

and Oprea

, Proofs of retrievability: theory and implementation, In Proceedings of the 2009 ACM workshop on Cloud computing security, CCSW’09, ACM Press, New York, 2009, pp. 43–54.

27.

, Liu

, Li

, Zomaya

A.Y.

, A framework of price bidding configurations for resource usage in cloud computing, IEEE Transactions on Parallel and Distributed Systems (99), 2015, pp. 1–14.

28.

, Tang

and Li

, Energy-efficient stochastic task scheduling on heterogeneous computing systems, IEEE Transactions on Parallel and Distributed Systems25(11) (2014)2867–2876.

29.

Pollari-Malmi

, Soisalon-Soininen

and Ylonen

, Concurrency control in B-trees with batch updates, IEEE Transactions on Knowledge and Data Engineering8(6) (1996)975–984.

30.

Armbrust

, Fox

, Griffith

, Joseph

A.D.

, et al., Above the clouds: A berkeley view of cloud computing, Technical Report UCB/EECS2009–28, EECS Department, University of California, Berkeley, 2009.

31.

Shah

M.A.

, Baker

, Mogul

J.C.

and Swaminathan

, Auditing to keep online storage services honest, In Proceedings of 11th USENIX workshop on Hot topics in operating systems(HOTOS’07), USENIX Association, Berkeley, 2007, 1–6.

32.

Bellare

and Goldreich

, On defining proofs of knowledge, In Advances in Cryptology - CRYPTO’ 92, Lecture Notes in Computer Science, 740(1993) Springer, pp. 390–420.

33.

Bellare

, Goldreich

and Goldwasser

, Incremental cryptography and application to virus protection, In Proceedings of 27th annual ACM symposium on Theory of computing (STOC ’95), ACM Press, New York, 1995, pp. 45–56.

34.

Goodrich

M.T.

, Papamanthou

, Tamassia

and Trian-dopoulos

, Athos: Efficient authentication of outsourced file systems, , In Proceedings of the 11th international conference on Information Security, ISC’08, Springer-Verlag, Berlin, Heidelberg, 2008, pp. 80–96.

35.

Sammeta

, Kannan

R.J.

and Parthiban

, Enhanced trusted third party for cyber security in multi cloud storage, In Proceedings of the 48th Annual Convention of Computer Society of India-Vol II, Springer, 2014, pp. 525–533.

36.

, Tang

, Veeravalli

, et al., Scheduling precedence constrained stochastic tasks on heterogeneous cluster systems, IEEE Transactions on Computers64(1) (2015)191–204.

37.

Goldreich

, Foundations of cryptography: Basic applications, Cambridge University Press, Cambridge, 2004.

38.

OpenSSL: The open source toolkit for SSL/TLS, http://www.openssl.org/.

39.

Gallagher

and Kerry

, Fips pub 186-4: Digital signature standard (DSS), National Institute of Standards and Technology (NIST), 2013.

40.

Maniatis

, Roussopoulous

, Giuli

, Rosenthal

, Baker

and Muliadi

, The LOCKSS peer-to-peer digital p-reservation system, ACM Transactions on computing Systems23(1) (2005)2–5.

41.

Kumar

P.S.

and Subramanlian

, Homomorpic distributed verification protocol for ensuring data storage security in cloud computing, Information-An International Interdisciplinary Journal14(10) (2011)3465–3476.

42.

Wang

, Wang

, Li

, Ren

and Lou

, Enabling public verifiability and data dynamics for storage security in cloud computing, In Proceedings of 14th European Symposium on Research in Computer Security(Esorics’ 09), Springer, Berlin, 2009, pp. 355–370.

43.

, Ai

, Tang

, et al., Hadoop recognition of biomedical named entity using conditional random fields, IEEE Transactions on Parallel and Distributed Systems26(11) (2015)3040–3051.

44.

Curtmola

, khan

and Burns

, Robust remote data checking, In Proceedings of 4th ACM international workshop on storage security and survivability(StorageSS’08), ACM Press, New York, 2008, pp. 63–68.

45.

Curtmola

, Khan

, Burns

and Ateniese

, MR-PDP: Multiple-replica provable data possession, In Proceedings of 28th International Conference on Distributed Computing Systems (ICDCS ’08), IEEE Press, New York, 2008, pp. 411–420.

46.

Rivest

R.L.

, Shamir

and Adleman

, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM21(2) (1978)120–126.

47.

Rijmen

and Daemen

, Advanced encryption standard, pp, In Proceedings of Federal Information Processing Standards Publications, National Institute of Standards and Technology (2001)19–22.

48.

Bolosky

W.J.

, Douceur

J.R.

, Ely

and Theirmer

, Feasability of a serverless distributed file system deployed on an existing set of desktop PCs, In Proceedings of the 2000 ACM international conference on Measurement and modeling of computer systems(SIGMETRICS ’00), ACM Press, New York, 2000, pp. 34–43.

49.

Dodis

, Vadhan

and Wichs

, Proofs of retrievability via hardness amplification, In Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography, TCC’09, Springer-Verlag, Berlin, Heidelberg, 2009, pp. 109–127.

50.

, Li

, He

, et al., A hybrid chemical reaction optimization scheme for task scheduling on heterogeneous computing systems, IEEE Transactions Parallel Distributed Systems26(12) (2015)3208–3222.

51.

Zhu

, Hu

, Ahn

G.J.

and Yu

, Cooperative provable data possession for integrity verification in multicloud storage, IEEE Transactions on Parallel and Distributed Systems23(2) (2012)2231–2244.

P 3 DP: privacy preserving provable data possession with multi-copy and data dynamics in a cloud storage

Abstract

Keywords

1 Introduction

1.1 Motivation

1.2 Our Contributions

2 The Problem and Definitions

2.1 The System Model

2.2 Problem Formalization

2.3 The Threat Model

2.4 Some Notations

2.5 The P3DP Scheme

2.6 Security Requirements

4 A Construction for P3DP

5 Security Analysis

7 Performance

7.1 Implementation

7.2 Experiments

8 Conclusions

Footnotes

Acknowledgments

References

2.5 The P³DP Scheme

4 A Construction for P³DP