Remote data checking using provable data possession

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

Research output: Contribution to journalArticle

248 Scopus citations

Abstract

We introduce a model for provable data possession (PDP) that can be used for remote data checking: A client that has stored data at an untrusted server can 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 is lightweight and supports large data sets in distributed storage systems. The model is also robust in that it incorporates mechanisms for mitigating arbitrary amounts of data corruption. We present two provably-secure PDP schemes that aremore efficient than previous solutions. In particular, the overhead at the server is low (or even constant), as opposed to linear in the size of the data. We then propose a generic transformation that adds robustness to any remote data checking scheme based on spot checking. 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. Finally, we conduct an in-depth experimental evaluation to study the tradeoffs in performance, security, and space overheads when adding robustness to a remote data checking scheme.

Original languageEnglish (US)
Article number12
JournalACM Transactions on Information and System Security
Volume14
Issue number1
DOIs
StatePublished - May 1 2011

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Computer Science(all)

Keywords

  • Archival storage
  • Cloud storage security
  • Erasure coding
  • Homomorphic verifiable tags
  • PDP
  • Provable data possession
  • Remote data checking
  • Robust auditing

Cite this

Ateniese, G., Burns, R., Curtmola, R., Herring, J., Khan, O., Kissner, L., Peterson, Z., & Song, D. (2011). Remote data checking using provable data possession. ACM Transactions on Information and System Security, 14(1), [12]. https://doi.org/10.1145/1952982.1952994