Provable data possession at untrusted stores
- 28 October 2007
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 2007, 598-609
- https://doi.org/10.1145/1315245.1315318
Abstract
We introduce a model for 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 system. 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. Copyright 2007 ACMThis publication has 21 references indexed in Scilit:
- The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard ModelLecture Notes in Computer Science, 2006
- The evolution of storage service providersPublished by Association for Computing Machinery (ACM) ,2005
- The LOCKSS peer-to-peer digital preservation systemACM Transactions on Computer Systems, 2005
- HMQV: A High-Performance Secure Diffie-Hellman ProtocolLecture Notes in Computer Science, 2005
- The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge ProtocolsLecture Notes in Computer Science, 2004
- Accountable-subgroup multisignaturesPublished by Association for Computing Machinery (ACM) ,2001
- Batch verifying multiple RSA digital signaturesElectronics Letters, 1998
- A digital multisignature scheme using bijective public-key cryptosystemsACM Transactions on Computer Systems, 1988
- On the generation of cryptographically strong pseudorandom sequencesACM Transactions on Computer Systems, 1983
- Riemann's hypothesis and tests for primalityJournal of Computer and System Sciences, 1976