RSA Laboratories

Proofs of Retrievability: Theory and Implementation

Citation: K. Bowers, A. Juels, and A. Oprea. Proofs of Retrievability: Theory and Implementation. ACM CCSW. 2009

Abstract: A proof of retrievability (POR) is a compact proof by a file system (prover) to a client (verifier) that a target file F is intact, in the sense that the client can fully recover it. As PORs incur lower communication complexity than transmission of F itself, they are an attractive building block for high-assurance remote storage systems. In this paper, we propose a theoretical framework for the design of PORs. Our framework improves the previously proposed POR constructions of Juels-Kaliski and Shacham-Waters, and also sheds light on the conceptual limitations of previous theoretical models for PORs. It supports a fully Byzantine adversarial model, carrying only the restriction—fundamental to all PORs—that the adversary’s error rate epsilon be bounded when the client seeks to extract F . Our techniques support efficient protocols across the full possible range of epsilon, up to epsilon non-negligibly close to 1. We propose a new variant on the Juels-Kaliski protocol and describe a prototype implementation. We demonstrate practical encoding even for files F whose size exceeds that of client main memory.

Click here for paper

Full Publication List