### Proofs of Retrievability: Theory and Implementation

Kevin D. Bowers, Ari Juels, and Alina Oprea

##### 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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
ajuels @ rsa com
History
2009-02-23: last of 3 revisions
See all versions
Short URL
https://ia.cr/2008/175

CC BY

BibTeX

@misc{cryptoeprint:2008/175,
author = {Kevin D.  Bowers and Ari Juels and Alina Oprea},
title = {Proofs of Retrievability: Theory and Implementation},
howpublished = {Cryptology ePrint Archive, Paper 2008/175},
year = {2008},
note = {\url{https://eprint.iacr.org/2008/175}},
url = {https://eprint.iacr.org/2008/175}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.