Paper 2008/432

Dynamic Provable Data Possession

C. Chris Erway, Alptekin Kupcu, Charalampos Papamanthou, and Roberto Tamassia

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 pre-processes the data and then sends it 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 has not been tampered with or deleted (without downloading the actual data). However, the original PDP scheme applies 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^{\epsilon}\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).

Note: This is the full version of CCS 2009 paper with the same title.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. CCS 2009
Keywords
outsourced storageauthenticated dictionaryauthenticated data structuresRSA treefile systemversion control systemuntrusted storageprovable data possessionskip listproof of retrievabilityintegrity checking
Contact author(s)
kupcu @ cs brown edu
History
2009-11-30: last of 3 revisions
2008-10-08: received
See all versions
Short URL
https://ia.cr/2008/432
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/432,
      author = {C.  Chris Erway and Alptekin Kupcu and Charalampos Papamanthou and Roberto Tamassia},
      title = {Dynamic Provable Data Possession},
      howpublished = {Cryptology ePrint Archive, Paper 2008/432},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/432}},
      url = {https://eprint.iacr.org/2008/432}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.