  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 the file given any "proving algorithm"
that has a sufficiently high success probability. This forms the basis of
\emph{proof-of-retrievability} ($\mathsf{PoR}$) systems.
  In this paper, we study multiple server $\mathsf{PoR}$ systems. We formalize
security definitions for two possible scenarios: (i) when a threshold of
servers succeed with high enough probability (worst-case) and (ii) when the
average of the success probability of all the servers is above a threshold
(average-case). We also motivate the study of confidentiality of the outsourced
message. We give $\mathsf{M}\mbox{-}\mathsf{PoR}$ schemes which are secure
under both these security definitions and provide reasonable confidentiality
guarantees even when there is no restriction on the computational power of the
servers. We also show how classical statistical techniques used by Paterson,
Stinson and Upadhyay (Journal of Mathematical Cryptology: 7(3)) can be extended
to evaluate whether the responses of the provers are accurate enough to permit
successful extraction. We also look at one specific instantiation of our
construction when instantiated with the unconditionally secure version of the
Shacham-Waters scheme (Asiacrypt, 2008). This scheme gives reasonable security
and privacy guarantee. We show that, in the multi-server setting with
computationally unbounded provers, one can overcome the limitation that the
verifier needs to store as much secret information as the provers.
