Proofs of retrievability: theory and implementation

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 be bounded when the client seeks to extract F. 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.

References

1. G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, and D. Song. Provable data possession at untrusted stores. In Proc. ACM CCS, pages 598--609, 2007.
2. G. Ateniese, R. Di Pietro, L. V. Mancini, and G. Tsudik. Scalable and efficient provable data possession, 2008. IACR ePrint manuscript 2008/114.
3. M. Bellare and A. Palacio. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In Proc. CRYPTO '04, pages 273--289. Springer, 2004. LNCS vol. 3152.
4. J. Black and P. Rogaway. Ciphers with arbitrary finite domains. In Proc. CT-RSA '02, pages 114--130. Springer, 2002. LNCS vol. 2271.
5. M. Blum, W. S. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. Algorithmica, 12(2/3):225--244, 1994.
6. K. Bowers, A. Juels, and A Oprea. Proofs of retrievability: Theory and implementation, 2008. Available from ePrint, report 2008/175.
7. R. Curtmola, O. Khan, and R. Burns. Robust remote data checking. In Proc. 4th ACM Workshop on Storage Security and Survivability (StorageSS), 2008.
8. Y. Dodis, S. Vadhan, and D. Wichs. Proofs of retrievability via hardness amplification. In TCC, 2009.
9. D.L.G. Filho and P.S.L.M. Barreto. Demonstrating data possession and uncheatable data transfer, 2006. IACR eArchive 2006/150. Referenced 2008 at http://eprint.iacr.org/2006/150.pdf.
10. O. Goldreich. Foundations of cryptography, Volume I: Basic tools. Cambridge University Press, 2001. First Edition.
11. O. Goldreich. Foundations of cryptography, Volume II: Basic applications. Cambridge University Press, 2004. First Edition.
12. P. Golle, S. Jarecki, and I. Mironov. Cryptographic primitives enforcing communication and storage complexity. In M. Blaze, editor, Proc. Financial Cryptography '02, pages 120--135. Springer, 2002. LNCS vol. 2357.
13. A. Juels and B. Kaliski. PORs: Proofs of retrievability for large files. In Proc. ACM CCS, pages 584--597, 2007.
14. M. Lillibridge, S. Elnikety, A. Birrell, M. Burrows, and M. Isard. A cooperative Internet backup scheme. In Proc. USENIX Annual Technical Conference, General Track 2003, pages 29--41, 2003.
15. M. Luby. LT codes. In Proc. Symposium on Foundations of Computer Science (FOCS), pages 271--282. IEEE, 2002.
16. M. Luby, M. Mitzenmacher, A. Shokrollahi, D. Spielman, and V. Stemann. Practical loss-resilient codes. In Proc. Symposium on Theory of Computation (STOC), page 150--159. ACM, 1997.
17. P. Maymounkov. On-line codes. Technical Report TR2002-833, Computer Science Department at New York University, November 2002.
18. M. Naor and G. N. Rothblum. The complexity of online memory checking. In Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 573--584, 2005.
19. J. Patarin. Improved security bounds for pseudorandom permutations. In Proc. ACM CCS, pages 142--150, 1997.
20. W. W. Peterson and E. J. Weldon, Jr. Error-Correcting Codes. MIT Press, 1972. Second Edition.
21. Hovav Shacham and Brent Waters. Compact proofs of retrievability. In Proc. ASIACRYPT '08, pages 90--107, Berlin, Heidelberg, 2008. Springer-Verlag.
22. M.A. Shah, M. Baker, J.C. Mogul, and R. Swaminathan. Auditing to keep online storage services honest, 2007. Presented at HotOS XI, May 2007.
23. A. Shokrollahi. Raptor codes. IEEE Transactions on Information Theory, 52(6):2551--2567, 2006.

Index Terms

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data encryption

• Security and privacy

  • Cryptography

• Theory of computation

  • Computational complexity and cryptography