Generic constructions of PoRs from codes and instantiations

Abstract

In this paper, we show how to construct – from any linear code – a Proof of Retrievability (𝖯𝗈𝖱{\mathsf{PoR}}) which features very low computation complexity on both the client (𝖵𝖾𝗋𝗂𝖿𝗂𝖾𝗋{\mathsf{Verifier}}) and the server (𝖯𝗋𝗈𝗏𝖾𝗋{\mathsf{Prover}}) sides, as well as small client storage (typically 512 bits). We adapt the security model initiated by Juels and Kaliski [PoRs: Proofs of retrievability for large files, Proceedings of the 2007 ACM Conference on Computer and Communications Security—CCS 2007, ACM, New York 2007, 584–597] to fit into the framework of Paterson, Stinson and Upadhyay [A coding theory foundation for the analysis of general unconditionally secure proof-of-retrievability schemes for cloud storage, J. Math. Cryptol. 7 2013, 3, 183–216], from which our construction evolves. We thus provide a rigorous treatment of the security of our generic design; more precisely, we sharply bound the extraction failure of our protocol according to this security model. Next we instantiate our formal construction with codes built from tensor-products as well as with Reed–Muller codes and lifted codes, yielding 𝖯𝗈𝖱{\mathsf{PoR}}s with moderate communication complexity and (server) storage overhead, in addition to the aforementioned features.

Keywords

• proof of retrievability
• error-correcting code
• cloud storage
• 11t71