  We consider the following problem that arises in outsourced storage: a user
stores her data $x$ on a remote server but wants to audit the server at some
later point to make sure it actually did store $x$. The goal is to design a
(randomized) verification protocol that has the property that if the server
passes the verification with some reasonably high probability then the user can
rest assured that the server is storing $x$.
  In this work we present an optimal solution (in terms of the user's storage
and communication) while at the same time ensuring that a server that passes
the verification protocol with any reasonable probability will store, to within
a small \textit{additive} factor, $C(x)$ bits of information, where $C(x)$ is
the plain Kolmogorov complexity of $x$. (Since we cannot prevent the server
from compressing $x$, $C(x)$ is a natural upper bound.) The proof of security
of our protocol combines Kolmogorov complexity with list decoding and unlike
previous work that relies upon cryptographic assumptions, we allow the server
to have unlimited computational power. To the best of our knowledge, this is
the first work that combines Kolmogorov complexity and list decoding.
  Our framework is general enough to capture extensions where the user splits
up $x$ and stores the fragment across multiple servers and our verification
protocol can handle non-responsive servers and colluding servers. As a
by-product, we also get a proof of retrievability. Finally, our results also
have an application in `storage enforcement' schemes, which in turn have an
application in trying to update a remote server that is potentially infected
with a virus.
