Monday, May 4, 2009
Tim Chaplin
Chair: Anita Jones; Westley Weimer
Advisor: abhi shelat
OLSSON 236D, 10:15:00
A Master's Thesis Presentation
Proofs of Retrievability
ABSTRACT
In this work we consider proofs of retrievability: consider a scenario in which a company has outsourced the storage of vital archival databases to an external service provider, such as Amazon S3. In this scenario, we expect the company to access this data seldomly, but for legal or economic reasons, it remains vital that the service provider be able to prove on a regular basis that the data is intact and retrievable. We revisit some simple solutions to this problem and show that they actually perform as well as their complex counterparts in a fair setting.
To create this fair setting, we introduce a model that enables apples-to-apples comparisons of differing solutions in terms of a security parameter beta and an encoding storage overhead parameter gamma. Using this model, we prove that surprisingly, all previous schemes have an asymptotically equivalent bandwidth cost of O(lg beta) in beta. In light of this, we argue that the key metrics for evaluating proof of retrievability schemes should be computational complexity and ease of implementation.
With this in mind, we adapt the sentinel scheme proposed by Juels and Kaliski and remove its principal limitation by enabling an unbounded number of verification interactions. We also strengthen its security guarantees. What results is a simple scheme with competitive bandwidth cost and minimal computational overhead. Furthermore, it could be implemented today against existing remote storage services such as Amazon S3 without the addition of any new or special server instructions.
Finally, we show how this new scheme can then be efficiently and practically combined with private information retrieval techniques to create a scheme whose bandwidth cost – namely O(lg beta lg(1 / gamma)) -- is asymptotically less than all prior schemes in terms of beta and gamma. This property is of theoretical interest, and may also be of practical use in a regime in which it is monetarily cost effective to trade computational complexity for storage overhead.