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.Category / Keywords: cryptographic protocols / Date: received 16 Apr 2008, last revised 23 Feb 2009 Contact author: ajuels at rsa com Available format(s): PDF | BibTeX Citation Version: 20090223:144657 (All versions of this report) Short URL: ia.cr/2008/175 Discussion forum: Show discussion | Start new discussion