Generic constructions of PoRs from codes and instantiations
Julien Lavauzelle, Françoise Levy-dit-Vehel · Journal of Mathematical Cryptology · 2019
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.