PORs are akin to other unorthodox cryptographic proof systems in the literature, such as proofs
of computational ability [40] and proofs of work (POWs) [21]. Memory-bound POWs [13] are similar
to the use of PORs for quality-of-service verification in that both types of proof aim to characterize
memory use in terms of the latency of the storage employed by the prover. Very close in spirit
to a POR is a construction of Golle, Jarecki, and Mironov [19], who investigate “storage-enforcing
commitment schemes.” Their schemes enable a prover to demonstrate that it is making use of storage
space at least |F |. The prover does not prove directly that it is storing file F , but proves that it is
has committed sufficient resources to do so.
The use of sentinels in our main scheme is similar is spirit to a number of other systems that
rely on the embedding of secret check values in files, such as the “ringers” used in [20]. There the
check values are easily verifiable computational tasks that provide evidence for the correct processing
of accompanying tasks. PORs bear an important operational difference in that they involve “spot
checks” or auditing, that is, the prover is challenged to reveal check values in isolation from the
rest of the file. The distinguishing feature of the POR protocols we propose here is the way that
they amplify the effectiveness of spot-checking for the special case of file-verification by combining
cryptographic hiding of sentinels with error-correction.
The earliest POR-like protocol of which we are aware is one proposed by Lillibridge et al. [25].
Their goal differs somewhat from ours in that they look to achieve assurance of the availability of a
file that is distributed across a set of servers in a peer relationship. To ensure that a file is intact,
Lillibridge et al. propose application of error-coding to a file combined with spot-checks of file blocks
conducted by system peers. Their approach assumes separate MACs on each block and does not
directly address error-correction for the single-server case, , and the paper does not establish formal
definitions or bounds on the verification procedure.
A more theoretical result of relevance is that of Naor and Rothblum (NR) [31]. They show that the
existence of a sub-linear-size proof of file recoverability implies the existence of one-way functions.
1
NR propose a proto col in which an error-correcting code is applied to a file F and blocks are then
MACed. By checking the integrity of a random subset of blocks, a verifier can obtain assurance
that the file as a whole is subject to recovery. NR also provide a simple, formal security definition
and prove security bounds on their construction. The NR security definition is similar to our formal
POR definition and more general, but is asymptotic, rather than concrete. Thus, in their proposed
scheme, NR consider encoding of an entire file as a single codeword in an error-correcting code. Such
encoding is inefficient in practice, but yields good theoretical prop erties. For our purposes, the NR
definition also omits some important elements. It assumes that the verifier has direct access to the
encoded file
˜
F , in essence that
˜
F is a fixed, published string. Thus the definition does not cover
the case of a server that rep orts file blocks in
˜
F inconsistently: In essence, the NR definition does
not define an extractor for F . Additionally, the NR definition does not capture the possibility of a
proof that relies on functional combination of file blo cks, rather than direct reporting of file blocks.
(We consider a POR scheme here, for instance, in which sentinels are XORed or hashed together to
reduce bandwidth.)
More recent work has considered the application of RSA-based hashing as a tool for constructing
proofs of recoverability. Filho and Barreto [16], for example, propose a scheme that makes indirect
use of a homomorphic RSA-based hash introduced by Shamir [34], briefly as follows. Let N be an
RSA modulus. The verifier stores k = F mod φ(N) for file F (suitably represented as an integer).
To challenge the prover to demonstrate retrievability of F , the verifier transmits a random element
g ∈ Z
N
. The prover returns s = g
F
mod N , and the verifier checks that g
k
mod N = s. This
protocol has the drawback of requiring the prover to exponentiate over the entire file F . In work
contemporaneous with our paper here, Ateniese et al. [3] have considered an elegant application
of RSA-based hashing to individual file blocks. In their scheme, homomorphic composition of file-
1
Note t hat our s entinel-based POR scheme interestingly does not require one-way functions, as sentinels
may be randomly generated. The contradiction stems from the fact that our scheme requires a key with
size linear in the number of protocol executions.