CryptoDB
Dynamic Provable Data Possession
| Authors: | |
|---|---|
| Download: | |
| Abstract: | As online storage-outsourcing services (e.g., Amazon's S3) and resource-sharing networks (e.g., peer-to-peer and grid networks) became popular, the problem of efficiently proving the integrity of data stored at untrusted servers has received increased attention. Ateniese et al. \cite{pdp} formalized this problem with a model called provable data possession (PDP). In this model, data is preprocessed by the client and then sent to an untrusted server for storage. The client can then challenge the server to prove that the data has not been tampered with or deleted (without sending the actual data). However, their PDP scheme applies only to static (or append-only) files. In reality, many outsourced storage applications (including network file systems and outsourced databases) need to handle dynamic data. This paper presents a definitional framework and an efficient construction for dynamic provable data possession (DPDP), which extends the PDP model to support provable updates to stored data (modifications to a block or insertion/deletion of a block). To achieve efficient DPDP, 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})$, for a file consisting of $n$ blocks, while maintaining the same probability of detection. Yet, our experiments show that this price is very low in practice, and hence our system is applicable to real scenarios. Our contributions can be summarized as defining the DPDP framework formally, and constructing the first fully dynamic PDP solution, which performs verification without downloading actual data and is very efficient. We also show how our DPDP scheme can be extended to construct complete file systems and version control systems (e.g., CVS) at untrusted servers, so that it can be used in complex outsourcing applications. |
BibTeX
@misc{eprint-2008-18128,
title={Dynamic Provable Data Possession},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / outsourced storage, authenticated dictionary, file system, version control system},
url={http://eprint.iacr.org/2008/432},
note={under submission kupcu@cs.brown.edu 14158 received 6 Oct 2008},
author={Chris Erway and Alptekin Küpçü and Charalampos Papamanthou and Roberto Tamassia},
year=2008
}