  There has been considerable recent interest in "cloud storage" wherein a user
asks a server to store a large file. One issue is whether the user can verify
that the server is actually storing the file, and typically a
challenge-response protocol is employed to convince the user that the file is
indeed being stored correctly. The security of these schemes is phrased in
terms of an extractor which will recover or retrieve the file given any
"proving algorithm" that has a sufficiently high success probability.
  This paper treats proof-of-retrievability schemes in the model of
unconditional security, where an adversary has unlimited computational power.
In this case retrievability of the file can be modelled as error-correction in
a certain code. We provide a general analytical framework for such schemes that
yields exact (non-asymptotic) reductions that precisely quantify conditions for
extraction to succeed as a function of the success probability of a proving
algorithm, and we apply this analysis to several archetypal schemes. In
addition, we provide a new methodology for the analysis of keyed POR schemes in
an unconditionally secure setting, and use it to prove the security of a
modified version of a scheme due to Shacham and Waters under a slightly
restricted attack model, thus providing the first example of a keyed POR scheme
with unconditional security. We also show how classical statistical techniques
can be used to evaluate whether the responses of the prover are accurate enough
to permit successful extraction. Finally, we prove a new lower bound on storage
and communication complexity of POR schemes.
