Paper 2007/202

Provable Data Possession at Untrusted Stores

Giuseppe Ateniese, Randal Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary Peterson, and Dawn Song


We introduce a model for {\em provable data possession} ($\pdp$) that allows a client that has stored data at an untrusted server to verify that the server possesses the original data without retrieving it. The model generates probabilistic proofs of possession by sampling random sets of blocks from the server, which drastically reduces I/O costs. The client maintains a constant amount of metadata to verify the proof. The challenge/response protocol transmits a small, constant amount of data, which minimizes network communication. Thus, the $\pdp$ model for remote data checking supports large data sets in widely-distributed storage systems. Previous work offers guarantees weaker than data possession, or requires prohibitive overhead at the server. We present two provably-secure $\pdp$ schemes that are more efficient than previous solutions, even when compared with schemes that achieve weaker guarantees. In particular, the overhead at the server is low (or even constant), as opposed to linear in the size of the data. Experiments using our implementation verify the practicality of $\pdp$ and reveal that the performance of $\pdp$ is bounded by disk I/O and not by cryptographic computation.

Note: December 7, 2007: Added important references and fixed some typos. October 12, 2007: We corrected a bug in the proof in which we erroneously assumed that the GCD of two parameters was 1 with overwhelming probability. The fix affects only the public verifiability feature of our main scheme but we now show how to achieve it by simply restricting the size of file blocks. See the Note at the end of the Introduction.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Full version of the ACM CCS 2007 paper.
Contact author(s)
ateniese @ cs jhu edu
2007-12-07: last of 4 revisions
2007-05-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giuseppe Ateniese and Randal Burns and Reza Curtmola and Joseph Herring and Lea Kissner and Zachary Peterson and Dawn Song},
      title = {Provable Data Possession at Untrusted Stores},
      howpublished = {Cryptology ePrint Archive, Paper 2007/202},
      year = {2007},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.