Paper 2007/243

PORs: Proofs of Retrievability for Large Files

Ari Juels and Burton S. Kaliski Jr.

Abstract

In this paper, we define and explore the notion of a _proof of retrievability_ (POR). A POR enables an archive or back-up service (prover) to demonstrate to a user (verifier) that it has ``possession'' of a file F, that is, that the archive retains data sufficient for the user to retrieve F in its entirety. A POR may be viewed as a kind of cryptographic proof of knowledge (POK), but one specially designed to handle a _large_ file (or bitstring) F. We explore POR protocols here in which the communication costs, number of memory accesses for the prover, and storage requirements of the user (verifier) are small parameters essentially independent of the length of $F$. In addition, in a POR, unlike a POK, neither the prover nor the verifier need actually have knowledge of F. PORs give rise to a new and unusual security definition. We view PORs as an important tool for the management of semi-trusted online archives. Existing cryptographic tools help users ensure the privacy and integrity of their files once they are retrieved. It is also natural, however, for users to want to verify that archives do not delete or modify files while they are stored. The goal of a POR is to accomplish these checks {\em without users having to download the files themselves}. A POR can also provide quality-of-service guarantees, i.e., show that a file is retrievable within a certain time bound.

Note: An up-to-date version of this paper is now maintained at ari-juels.com.