Provable data possession at untrusted stores

TLDR

The paper proposes a provable data possession model enabling clients to verify that an untrusted server holds original data without downloading it. The model uses probabilistic proofs based on random block sampling, with constant client metadata and a lightweight challenge/response protocol to keep I/O and network costs low. The PDP model supports large datasets in distributed storage systems.

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.