Remote data checking using provable data possession
Authors:
Top Cited Papers
Open Access
- 1 May 2011
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Information and System Security
- Vol. 14 (1) , 1-34
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 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.Keywords
This publication has 39 references indexed in Scilit:
- Proofs of retrievability2009
- HAIL2009
- Scalable and efficient provable data possession2008
- Provable data possession at untrusted stores2007
- Towards Plaintext-Aware Public-Key Encryption Without Random Oracles2004
- The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols2004
- Aggregate and Verifiably Encrypted Signatures from Bilinear Maps2003
- Ciphers with Arbitrary Finite Domains2002
- The Exact Security of Digital Signatures-How to Sign with RSA and Rabin1996
- Random oracles are practical1993