Provable data possession at untrusted stores

ABSTRACT

We introduce a model for provable data possession (PDP) that allows a client that has stored data at an untrusted server to verify that the server possesses the original data without retrieving it. The model generates probabilistic proofs of possession by sampling random sets of blocks from the server, which drastically reduces I/O costs. The client maintains a constant amount of metadata to verify the proof. The challenge/response protocol transmits a small, constant amount of data, which minimizes network communication. Thus, the PDP model for remote data checking supports large data sets in widely-distributed storage system.

We present two provably-secure PDP schemes that are more efficient than previous solutions, even when compared with schemes that achieve weaker guarantees. In particular, the overhead at the server is low (or even constant), as opposed to linear in the size of the data. Experiments using our implementation verify the practicality of PDP and reveal that the performance of PDP is bounded by disk I/O and not by cryptographic computation.

REFERENCES

• 1: M. Abe and S. Fehr. Perfect NIZK with adaptive soundness. In Proc. of Theory of Cryptography Conference (TCC '07), 2007. Full version available on Cryptology ePrint Archive, Report 2006/423.
• 2: J. Aspnes, J. Feigenbaum, A Yampolskiy, and S. Zhong. Towards a theory of data entanglement. In Proc. of Euro. Symp. on Research in Computer Security, 2004.
• 3: G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, and D. Song. Provable data possession at untrusted stores. Cryptology ePrint archive, May 2007. Report 2007/202.
• 4: M. Bellare, J. Garay, and T. Rabin. Fast batch verification for modular exponentiation and digital signatures. In Proc. of EUROCRYPT '98, LNCS, pages 236--250, 1998.
• 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 Proc. of CRYPTO '04, LNCS, pages 273--289. Springer, 2004.
• 7: M. Bellare and A. Palacio. Towards plaintext-aware public-key encryption without random oracles. In Proc. of ASIACRYPT '04, volume 3329 of LNCS, pages 48--62. Springer, 2004.
• 8: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 9: M. Bellare and P. Rogaway. The exact security of digital signatures - How to sign with RSA and Rabin. In EUROCRYPT, pages 399--416, 1996.
• 10: M. Bellare and P. Rogaway. PSS: Provably secure encoding method for digital signatures. IEEE P1363a: Provably secure signatures, 1998. http://grouper.ieee.org/groups/1363/P1363a/PSSigs.html.
• 11: 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
• 12: M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. In Proc. of FOCS '95.
• 13: D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. In Proc. of EUROCRYPT '03, pages 416--432, 2003.
• 14: Ivan Damgård, Towards Practical Public Key Systems Secure Against Chosen Ciphertext Attacks, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.445-456, August 11-15, 1991
• 15: A. W. Dent. The hardness of the DHK problem in the generic group model. Cryptology ePrint Archive, Report 2006/156.
• 16: A. W. Dent. The Cramer-Shoup encryption scheme is plaintext aware in the standard model. In Proc. of EUROCRYPT '06, volume 4004 of LNCS, pages 289--307. Springer, 2006.
• 17: Y. Deswarte, J.-J. Quisquater, and A. Saidane. Remote integrity checking. In Proc. of Conference on Integrity and Internal Control in Information Systems '03, Nov 2003.
• 18: Amos Fiat, Batch RSA, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.175-185, August 20-24, 1989
• 19: D. L. G. Filho and P. S L. M. Baretto. Demonstrating data possession and uncheatable data transfer. IACR ePrint archive, 2006. Report 2006/150.
• 20: P. Golle, S. Jarecki, and I. Mironov. Cryptographic primitives enforcing communication and storage complexity. In Proc. of Financial Cryptography, 2002.
• 21: Satoshi Hada , Toshiaki Tanaka, On the Existence of 3-Round Zero-Knowledge Protocols, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.408-423, August 23-27, 1998
• 22: L. Harn. Batch verifying multiple RSA digital signatures. Electronics Letters, 34(12):1219--1220, 1998.
• 23: Ragib Hasan , William Yurcik , Suvda Myagmar, The evolution of storage service providers: techniques and challenges to outsourcing storage, Proceedings of the 2005 ACM workshop on Storage security and survivability, November 11-11, 2005, Fairfax, VA, USA [doi>10.1145/1103780.1103782]
• 24: Robert Johnson , David Molnar , Dawn Xiaodong Song , David Wagner, Homomorphic Signature Schemes, Proceedings of the The Cryptographer's Track at the RSA Conference on Topics in Cryptology, p.244-262, February 18-22, 2002
• 25: A. Juels and B. S. Kaliski. PORs: Proofs of retrievability for large files. Cryptology ePrint archive, June 2007. Report 2007/243.
• 26: Mahesh Kallahalla , Erik Riedel , Ram Swaminathan , Qian Wang , Kevin Fu, Plutus: Scalable Secure File Sharing on Untrusted Storage, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 27: H. Krawczyk. HMQV: A high-performance secure Diffie-Hellman protocol. In Proc. of CRYPTO '05, volume 3621 of LNCS, pages 546--566. Springer, 2005.
• 28: M. N. Krohn, M. J. Freedman, and D. Mazières. On-the-fly verification of rateless erasure codes for efficient content distribution. In Proc. of the IEEE Symposium S&P, 2004.
• 29: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 30: Jinyuan Li , Maxwell Krohn , David Mazières , Dennis Shasha, Secure untrusted data repository (SUNDR), Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.9-9, December 06-08, 2004, San Francisco, CA
• 31: Umesh Maheshwari , Radek Vingralek , William Shapiro, How to build a trusted database system on untrusted storage, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.10-10, October 22-25, 2000, San Diego, California
• 32: Petros Maniatis , Mema Roussopoulos , T. J. Giuli , David S. H. Rosenthal , Mary Baker, The LOCKSS peer-to-peer digital preservation system, ACM Transactions on Computer Systems (TOCS), v.23 n.1, p.2-50, February 2005 [doi>10.1145/1047915.1047917]
• 33: Silvio Micali , Kazuo Ohta , Leonid Reyzin, Accountable-subgroup multisignatures: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502017]
• 34: G. L. Miller. Riemann's hypothesis and tests for primality. JCSS, 13(3):300--317, 1976.
• 35: Athicha Muthitacharoen , Robert Morris , Thomer M. Gil , Benjie Chen, Ivy: a read/write peer-to-peer file system, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060293]
• 36: E. Mykletun, M. Narasimha, and G. Tsudik. Authentication and integrity in outsourced databases. In Proc. of NDSS '04.
• 37: 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]
• 38: Tatsuaki Okamoto, A digital multisignature scheme using bijective public-key cryptosystems, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.432-441, Nov. 1988 [doi>10.1145/48012.48246]
• 39: A. Oprea, M. K. Reiter, and K. Yang. Space-efficient block storage integrity. In Proc. of NDSS '05, 2005.
• 40: 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]
• 41: F. Sebe, A. Martinez-Balleste, Y. Deswarte, J. Domingo-Ferrer, and J.-J. Quisquater. Time-bounded remote file integrity checking. Technical Report 04429, LAAS, July 2004.
• 42: Mehul A. Shah , Mary Baker , Jeffrey C. Mogul , Ram Swaminathan, Auditing to keep online storage services honest, Proceedings of the 11th USENIX workshop on Hot topics in operating systems, p.1-6, May 07-09, 2007, San Diego, CA
• 43: Adi Shamir, On the generation of cryptographically strong pseudorandom sequences, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.38-44, Feb. 1983 [doi>10.1145/357353.357357]
• 44: D. Thompson and J. Best. The future of magnetic data storage technology. IBM Journal Research and Development, 44(3):311--319, May 2000.
• 45: Marc Waldman , David Mazières, Tangler: a censorship-resistant publishing system based on document entanglements, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502002]
• 46: Aydan R. Yumerefendi , Jeffrey S. Chase, Strong accountability for network storage, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.6-6, February 13-16, 2007, San Jose, CA

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

General Terms:
Performance, Security

Keywords:
archival storage, homorphic verifiable tags, pdp, provable data possession, storage security