Do You Have My Data? Prove it! (Provable Data Possession at Untrusted Stores)

Oct 03, 2007

Abstract

Faced with cost and regulatory considerations, many companies are
outsourcing the storage of their data to third parties. Outsourcing data
storage achieves economies of scale for the management of storage and
avoids the large initial investment to set up data centers. Recently, many
such online archival systems have emerged from within the research and
industrial communities.

In storage oursourcing, a client sends data to a server, which is required
by contract to provide persistent archival of the data. Since the server
is not trusted and may misbehave, the client typically retains a small
piece of metadata which is used to verify the authenticity of the data
upon its retrieval. The problem is that by the time data is retrieved, it
might be already too late to recover lost or damaged data. Current systems
lack a basic guarantee: Proving data possession upon a user's request
(usually before data retrieval).

In this presentation we introduce a model for provable data posession
(PDP) which allows a client that has stored data at an untrusted server to
verify that the server possesses the original data without retrieving it.
We present provably-secure PDP schemes that have low (or even constant)
overhead at the server and and minimize network communication by
transmitting a small, constant, amount of data for every
challenge/response.

This presentation is based on joint work with Giuseppe Ateniese, Randal
Burns, Joseph Herring, Lea Kissner, Zachary Peterson and Dawn Song. A
complete description is available on the Cryptology ePrint archive at
http://eprint.iacr.org/2007/202.