Generic constructions of PoRs from codes and instantiations

In this paper, we show how to construct-from any linear code- A Proof of Retrievability (PoR) which features very low computation complexity on both the client (Verifier) and the server (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 PoRs with moderate communication complexity and (server) storage overhead, in addition to the aforementioned features.