MR-PDP: Multiple-Replica Provable Data Possession

TLDR

Many storage systems rely on replication to improve availability and durability, yet they provide no strong evidence that multiple copies are actually stored, allowing colluding servers to feign multiple replicas. This work proposes multiple‑replica provable data possession (MR‑PDP) to let a client verify that each of its t replicas can be produced and that the system uses t times the storage of a single replica. MR‑PDP is a provably secure challenge‑response protocol that lets a client prove the existence of each unique replica and the proportional storage usage. MR‑PDP is computationally more efficient than running single‑replica PDP on t separate files and can cheaply generate additional replicas when existing ones fail.

Abstract

Many storage systems rely on replication to increase the availability and durability of data on untrusted storage systems. At present, such storage systems provide no strong evidence that multiple copies of the data are actually stored. Storage servers can collude to make it look like they are storing many copies of the data, whereas in reality they only store a single copy. We address this shortcoming through multiple-replica provable data possession (MR-PDP): A provably-secure scheme that allows a client that stores t replicas of a file in a storage system to verify through a challenge-response protocol that (1) each unique replica can be produced at the time of the challenge and that (2) the storage system uses t times the storage required to store a single replica. MR-PDP extends previous work on data possession proofs for a single copy of a file in a client/server storage system (Ateniese et al., 2007). Using MR-PDP to store t replicas is computationally much more efficient than using a single-replica PDP scheme to store t separate, unrelated files (e.g., by encrypting each file separately prior to storing it). Another advantage of MR-PDP is that it can generate further replicas on demand, at little expense, when some of the existing replicas fail.