Dynamic Provable Data Possession

TLDR

Storage outsourcing and resource‑sharing networks have made proving data integrity on untrusted servers a key concern, and the Provable Data Possession model allows a client to store data with minimal metadata and later verify that the data have not been tampered with or deleted, but existing PDP schemes only support static or append‑only files. The authors propose a framework and efficient constructions for Dynamic Provable Data Possession (DPDP) that enable provable updates to stored data. They employ authenticated dictionaries built on rank information and demonstrate how the DPDP scheme can be integrated into outsourced file systems and version control systems such as CVS. The dynamic updates incur a cost of O(log n) (or O(n ε log n)) per block while preserving or improving the probability of detecting misbehavior, and empirical tests show the overhead is minimal—proofs of 415 KB and 30 ms computation for a 1 GB file.

Abstract

As storage-outsourcing services and resource-sharing networks have become popular, the problem of efficiently proving the integrity of data stored at untrusted servers has received increased attention. In the Provable Data Possession (PDP) model, the client preprocesses the data and then sends them to an untrusted server for storage while keeping a small amount of meta-data. The client later asks the server to prove that the stored data have not been tampered with or deleted (without downloading the actual data). However, existing PDP schemes apply only to static (or append-only) files. We present a definitional framework and efficient constructions for Dynamic Provable Data Possession (DPDP), which extends the PDP model to support provable updates to stored data. We use a new version of authenticated dictionaries based on rank information. The price of dynamic updates is a performance change from O (1) to O (log n (or O ( n ε log n )) for a file consisting of n blocks while maintaining the same (or better, respectively) probability of misbehavior detection. Our experiments show that this slowdown is very low in practice (e.g., 415KB proof size and 30ms computational overhead for a 1GB file). We also show how to apply our DPDP scheme to outsourced file systems and version control systems (e.g., CVS).