Storage Enforcement with Kolmogorov Complexity and List Decoding

Details Storage Enforcement with Kolmogorov Complexity and List Decoding Storage Enforcement with Kolmogorov Complexity and List Decoding

2011-04-15

arxiv.org/abs/1104.3025v1

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Storage Enforcement with Kolmogorov Complexity and List Decoding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Storage Enforcement with Kolmogorov Complexity and List Decoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Storage Enforcement with Kolmogorov Complexity and List Decoding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8763