Thoughts on Provable Data Possession at Untrusted Stores

Authors: Giuseppe Ateniese† Randal Burns† Reza Curtmola† Joseph Herring†
Lea Kissner ‡ Zachary Peterson† Dawn Song §

†Department of Computer Science, Johns Hopkins
University, Baltimore, MD – {ateniese, randal,
crix}@cs.jhu.edu, jrh@jhu.edu, zachary@cs.jhu.edu
‡Google, Inc. – leak@cs.cmu.edu
§University of California Berkeley/Carnegie Mellon Univer-
sity – dawnsong@cs.berkeley.edu

Venue: CCS’07, October 29–November 2, 2007, Alexandria, Virginia, USA

Paper: http://www.cs.berkeley.edu/~dawnsong/papers/p598-ateniese

Summary:
The authors describe a way to probabilistically determine whether a file stored at a SSP exists and has not been modified. I don't quite understand the crypto, but the results are:

• Fast checks. They are I/O bound, not CPU bound
• The size of the file stored at the server increases
• The client needs to store a constant small amount of data per file
• They use sampling to reduce the load on the server.
• Uploads are slow because preprocessing is expensive on the order of 160kB/s

This work is almost identical work by Ari Juels(RSA Labs) and Burton Kaliski(EMC Corp) PORs: Proofs-of-Retrievability for Large Files. However, in PORs, a client has to decide the number of checks a priori because the system works by encoding a constant number of sentinel blocks for checks in the file that are queried and hence consumed during challenges.

The main difference between PORs and PDPs is: PORs prove to a client that the entire file can be retrieved unmodified. PDPs do not make this claim. They only claim the file blocks tested are uncorrupted.