Remote data checking using provable data possession
Top Cited Papers
- 1 May 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Information and System Security
- Vol. 14 (1), 1-34
- https://doi.org/10.1145/1952982.1952994
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 31 references indexed in Scilit:
- Proofs of retrievabilityPublished by Association for Computing Machinery (ACM) ,2009
- HAILPublished by Association for Computing Machinery (ACM) ,2009
- Scalable and efficient provable data possessionPublished by Association for Computing Machinery (ACM) ,2008
- Provable data possession at untrusted storesPublished by Association for Computing Machinery (ACM) ,2007
- Towards Plaintext-Aware Public-Key Encryption Without Random OraclesLecture Notes in Computer Science, 2004
- The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge ProtocolsLecture Notes in Computer Science, 2004
- Aggregate and Verifiably Encrypted Signatures from Bilinear MapsLecture Notes in Computer Science, 2003
- Ciphers with Arbitrary Finite DomainsLecture Notes in Computer Science, 2002
- The Exact Security of Digital Signatures-How to Sign with RSA and RabinLecture Notes in Computer Science, 1996
- Random oracles are practicalPublished by Association for Computing Machinery (ACM) ,1993