10.1184/R1/6469184.v1 Giuseppe Ateniese Giuseppe Ateniese Randal Burns Randal Burns Reza Curtmola Reza Curtmola Joseph Herring Joseph Herring Lea Kissner Lea Kissner Zachary Peterson Zachary Peterson Dawn Song Dawn Song Provable Data Possession at Untrusted Stores Carnegie Mellon University 2007 provable data possession PDP homomorphic verifiable tags archival storage storage security 2007-01-01 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/Provable_Data_Possession_at_Untrusted_Stores/6469184 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 systems. 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.