Pors: proofs of retrievability for large files

ABSTRACT

In this paper, we define and explore proofs of retrievability (PORs). A POR scheme enables an archive or back-up service (prover) to produce a concise proof that a user (verifier) can retrieve a target file F, that is, that the archive retains and reliably transmits file data sufficient for the user to recover F in its entirety.

A POR may be viewed as a kind of cryptographic proof of knowledge (POK), but one specially designed to handle a large file (or bitstring) F. We explore POR protocols here in which the communication costs, number of memory accesses for the prover, and storage requirements of the user (verifier) are small parameters essentially independent of the length of F. In addition to proposing new, practical POR constructions, we explore implementation considerations and optimizations that bear on previously explored, related schemes.

In a POR, unlike a POK, neither the prover nor the verifier need actually have knowledge of F. PORs give rise to a new and unusual security definition whose formulation is another contribution of our work.

We view PORs as an important tool for semi-trusted online archives. Existing cryptographic techniques help users ensure the privacy and integrity of files they retrieve. It is also natural, however, for users to want to verify that archives do not delete or modify files prior to retrieval. The goal of a POR is to accomplish these checks without users having to download the files themselves. A POR can also provide quality-of-service guarantees, i.e., show that a file is retrievable within a certain time bound.

REFERENCES

• 1: Amazon.com. Amazon simple storage service (Amazon S3), 2007. Referenced 2007 at aws.amazon.com/s3.
• 2: Amin Shokrollahi, Raptor codes, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2551-2567, June 2006 [doi>10.1109/TIT.2006.874390]
• 3: G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, and D. Song. Provable data possession at untrusted stores, 2007. To appear.
• 4: R. Bazzi and Y. Ding. Non-skipping timestamps for Byzantine data storage systems. In R. Guerraoui, editor, DISC '04, pages 405--419. Springer, 2004. LNCS vol. 3274.
• 5: Mihir Bellare , Oded Goldreich, On Defining Proofs of Knowledge, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.390-420, August 16-20, 1992
• 6: M. Bellare and A. Palacio. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In CRYPTO '04, pages 273--289. Springer, 2004. LNCS vol. 3152.
• 7: John Black , Phillip Rogaway, Ciphers with Arbitrary Finite Domains, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.114-130, February 18-22, 2002
• 8: M. Blum, W. S. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. Algorithmica, 12(2/3):225--244, 1994.
• 9: Christian Cachin , Stefano Tessaro, Asynchronous Veri.able Information Dispersal, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.191-202, October 26-28, 2005 [doi>10.1109/RELDIS.2005.9]
• 10: Christian Cachin , Stefano Tessaro, Optimal Resilience for Erasure-Coded Byzantine Distributed Storage, Proceedings of the International Conference on Dependable Systems and Networks, p.115-124, June 25-28, 2006 [doi>10.1109/DSN.2006.56]
• 11: Dwaine Clarke , G. Edward Suh , Blaise Gassend , Ajay Sudan , Marten van Dijk , Srinivas Devadas, Towards Constant Bandwidth Overhead Integrity Checking of Untrusted Data, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.139-153, May 08-11, 2005
• 12: Brian F. Cooper , Hector Garcia-Molina, Peer-to-peer data trading to preserve information, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.133-170, April 2002 [doi>10.1145/506309.506310]
• 13: C. Dwork, A. Goldberg, and M. Naor. On memory-bound functions for fighting spam. In D. Boneh, editor, CRYPTO '03, pages 426--444. Springer, 2003. LNCS vol. 2729.
• 14: I. D. C. J. F. Gantz et al. The Expanding Digital Universe: A Forecast of Worldwide Information Growth through 2010, March 2007. Whitepaper.
• 15: J. Feldman. Using many machines to handle an enormous error-correcting code. In IEEE Information Theory Workshop (ITW), 2006. Referenced 2007 at http://www.columbia.edu/~jf2189/pubs/bigcode.pdf.
• 16: D. L. G. Filho and P. S. L. M. Barreto. Demonstrating data possession and uncheatable data transfer, 2006. IACR eArchive 2006/150. Referenced 2007 at http://eprint.iacr.org/2006/150.pdf.
• 17: O. Goldreich, Randomness, interactive proofs, and zero-knowledge—A survey, A half-century survey on The Universal Turing Machine, p.377-405, October 1988, Berlin, Germany
• 18: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 19: P. Golle, S. Jarecki, and I. Mironov. Cryptographic primitives enforcing communication and storage complexity. In M. Blaze, editor, Financial Cryptography '02, pages 120--135. Springer, 2002. LNCS vol. 2357.
• 20: Philippe Golle , Ilya Mironov, Uncheatable Distributed Computations, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.425-440, April 08-12, 2001
• 21: Markus Jakobsson , Ari Juels, Proofs of Work and Bread Pudding Protocols, Proceedings of the IFIP TC6/TC11 Joint Working Conference on Secure Information Networks: Communications and Multimedia Security, p.258-272, September 20-21, 1999
• 22: Vishal Kher , Yongdae Kim, Securing distributed storage: challenges, techniques, and systems, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103780.1103783]
• 23: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 24: L. Lamport. On interprocess communication. Part II: Algorithms. Distributed Computing, 1(2):86--101, 1986.
• 25: Mark Lillibridge , Sameh Elnikety , Andrew Birrell , Mike Burrows , Michael Isard, A cooperative internet backup scheme, Proceedings of the annual conference on USENIX Annual Technical Conference, p.3-3, June 09-14, 2003, San Antonio, Texas
• 26: H. Lipmaa. An oblivious transfer protocol with log-squared communication. In J. Zhou and J. Lopez, editors, Information Security Conference (ISC) '05, pages 314--328. Springer, 2005. LNCS vol. 3650.
• 27: Moses Liskov , Ronald L. Rivest , David Wagner, Tweakable Block Ciphers, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.31-46, August 18-22, 2002
• 28: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 29: Dahlia Malkhi , Michael K. Reiter, An Architecture for Survivable Coordination in Large Distributed Systems, IEEE Transactions on Knowledge and Data Engineering, v.12 n.2, p.187-202, March 2000 [doi>10.1109/69.842262]
• 30: Jean-Philippe Martin , Lorenzo Alvisi , Michael Dahlin, Minimal Byzantine Storage, Proceedings of the 16th International Conference on Distributed Computing, p.311-325, October 28-30, 2002
• 31: Moni Naor , Guy N. Rothblum, The Complexity of Online Memory Checking, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.573-584, October 23-25, 2005 [doi>10.1109/SFCS.2005.71]
• 32: E. St. Pierre. ILM: Tiered services and the need for classification. In Storage Networking World (SNW) '07, April 2007. Slide presentation.
• 33: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 34: R. Rivest. The pure crypto project's hash function. Cryptography Mailing List Posting. Referenced 2007 at http://diswww.mit.edu/bloom-picayune/crypto/13190.
• 35: P. Rogaway. Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In P. J. Lee, editor, ASIACRYPT '04, pages 16--31. Springer, 2004. LNCS vol. 3329.
• 36: Kouichi Sakurai , Toshiya Itoh, On the Discrepancy between Serial and Parallel of Zero-Knowledge Protocols (Extended Abstract), Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.246-259, August 16-20, 1992
• 37: 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. Referenced 2007 at http://www.hpl.hp.com/ personal/Mehul_Shah/papers/hotos11_2007_shah.pdf.
• 38: X. Shen , A. Choudhary , C. Matarazzo , P. Sinha, A Distributed Multi-Storage Resource Architecture and I/O Performance Prediction for Scientific Computing, Cluster Computing, v.6 n.3, p.189-200, July 2003 [doi>10.1023/A:1023584319229]
• 39: R. Sion and B. Carbunar. On the computational practicality of private information retrieval. In Network and Distributed Systems Security Symposium (NDSS) '07, 2007. To appear.
• 40: Moti Yung, Zero-knowledge proofs of computational power (extended summary), Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.196-207, November 1990, Houthalen, Belgium

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  E. Data
  E.5 FILES
      Subjects: Backup/recovery

General Terms:
Algorithms, Measurement, Reliability, Security, Theory

Keywords:
proofs of knowledge, proofs of retrievability, storage security, storage systems