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.
Category / Keywords: cryptographic protocols / Date: received 18 Jun 2007, withdrawn 8 Nov 2007 Contact author: ajuels at rsa com Available format(s): (-- withdrawn --) Note: An up-to-date version of this paper is now maintained at ari-juels.com. Version: 20071108:201253 (All versions of this report) Short URL: ia.cr/2007/243