Robust remote data checking

ABSTRACT

Remote data checking protocols, such as provable data possession (PDP) [1], allow clients that outsource data to untrusted servers to verify that the server continues to correctly store the data. Through the careful integration of forward error-correcting codes and remote data checking, a system can prove possession with arbitrarily high probability. We formalize this notion in the robust data possession guarantee. We distill the key performance and security requirements for integrating forward error-correcting codes into PDP and describe an encoding scheme and file organization for robust data possession that meets these requirements. We give a detailed analysis of this scheme and build a Monte-Carlo simulation to evaluate tradeoffs in reliability, space overhead, and performance. A practical way to evaluate these tradeoffs is an essential input to system design, allowing the designer to choose the encoding and data checking protocol parameters that realize robust data possession.

REFERENCES

• 1: Giuseppe Ateniese , Randal Burns , Reza Curtmola , Joseph Herring , Lea Kissner , Zachary Peterson , Dawn Song, Provable data possession at untrusted stores, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315318]
• 2: Giuseppe Ateniese , Roberto Di Pietro , Luigi V. Mancini , Gene Tsudik, Scalable and efficient provable data possession, Proceedings of the 4th international conference on Security and privacy in communication netowrks, September 22-25, 2008, Istanbul, Turkey [doi>10.1145/1460877.1460889]
• 3: K. Bowers, A. Juels, and A. Oprea. Proofs of retrievability: Theory and implementation. ePrint Archive Report, (2008/175), 2008.
• 4: Reza Curtmola , Osama Khan , Randal Burns , Giuseppe Ateniese, MR-PDP: Multiple-Replica Provable Data Possession, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.411-420, June 17-20, 2008 [doi>10.1109/ICDCS.2008.68]
• 5: E.-J. Goh, H. Shacham, N. Modadugu, and D. Boneh. Sirius: Securing remote untrusted storage. In Proc. of NDSS'03, 2003.
• 6: Ari Juels , Burton S. Kaliski, Jr., Pors: proofs of retrievability for large files, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315317]
• 7: Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin, SafeStore: a durable and practical storage system, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 8: M. N. Krohn, M. J. Freedman, and D. Mazières. On-the-fly verification of rateless erasure codes for efficient content distribution. In IEEE Symposium on Security and Privacy, 2004.
• 9: Michael G. Luby , Michael Mitzenmacher , M. Amin Shokrollahi , Daniel A. Spielman , Volker Stemann, Practical loss-resilient codes, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.150-159, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258573]
• 10: P. Maymounkov and D. Mazieres. Rateless codes and big downloads. In International Workshop on Peer-to-Peer Systems, 2003.
• 11: David Mazières , Dennis Shasha, Building secure file systems out of byzantine storage, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571840]
• 12: M. Mitzenmacher. Digital fountains: A survey and look forward. In IEEE Information Theory Workshop, 2004.
• 13: I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2):300--304, 1960.
• 14: Thomas S. J. Schwarz , Ethan L. Miller, Store, Forget, and Check: Using Algebraic Signatures to Check Remotely Administered Storage, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.12, July 04-07, 2006 [doi>10.1109/ICDCS.2006.80]
• 15: H. Shacham and B. Waters. Compact proofs of retrievability. ePrint Archive Report, (2008/073), 2008.
• 16: M. A. Shah, R. Swaminathan, and M. Baker. Privacy-preserving audit and extraction of digital contents. ePrint Archive Report, (2008/186).

INDEX TERMS

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

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
  E.4 CODING AND INFORMATION THEORY

General Terms:
Performance, Reliability, Security

Keywords:
archival storage, error-correcting codes, pdp, provable data possession, remote data checking, spot checking, storage security