Remote data checking using provable data possession
Giuseppe Ateniese, Randal C. Burns, Reza Curtmola et al. · ACM Transactions on Information and System Security · 2011
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 are more 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.
Cited by 394 works. doi:10.1145/1952982.1952994
Authors
- Giuseppe Ateniese
- Randal C. Burns
- Reza Curtmola
- Osama Khan
- Lea Kissner
- Zachary N. J. Peterson
- Dawn Xiaodong Song
References
- Lecture Notes in Computer Science 1205
- Random oracles are practical
- Riemann's hypothesis and tests for primality
- OceanStore
- Advances in Cryptology — CRYPTO’ 99
- Provable data possession at untrusted stores
- Practical loss-resilient codes
- The Exact Security of Digital Signatures-How to Sign with RSA and Rabin
- On the generation of cryptographically strong pseudorandom sequences
- Pors