Giuseppe Ateniese
Roberto Di Pietro
Gene Tsudik
ABSTRACT
Storage outsourcing is a rising trend which prompts a number of interesting security issues, many of which have been extensively investigated in the past. However, Provable Data Possession (PDP) is a topic that has only recently appeared in the research literature. The main issue is how to frequently, efficiently and securely verify that a storage server is faithfully storing its client's (potentially very large) outsourced data. The storage server is assumed to be untrusted in terms of both security and reliability. (In other words, it might maliciously or accidentally erase hosted data; it might also relegate it to slow or off-line storage.) The problem is exacerbated by the client being a small computing device with limited resources. Prior work has addressed this problem using either public key cryptography or requiring the client to outsource its data in encrypted form.
In this paper, we construct a highly efficient and provably secure PDP technique based entirely on symmetric key cryptography, while not requiring any bulk encryption. Also, in contrast with its predecessors, our PDP technique allows outsourcing of dynamic data, i.e, it efficiently supports operations, such as block modification, deletion and append.
- 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.Google Scholar
Cross Ref
- G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, and D. Song. Provable data possession at untrusted stores. In ACM CCS'07, Full paper available on e-print (2007/202), 2007. Google ScholarDigital Library
- G. Ateniese, D. Chou, B. de Medeiros, and G. Tsudik. Sanitizable signatures. In ESORICS'05, 2005.Google ScholarDigital Library
- B. Preneel, et al. NESSIE D21 - performance of optimized implementations of the nessie primitives.Google Scholar
- M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. In CRYPTO'96, 1996. Google ScholarDigital Library
- M. Bellare, R. Guérin, and P. Rogaway. XOR MACs: New methods for message authentication using finite pseudorandom functions. In CRYPTO'95, 1995. Google ScholarDigital Library
- J. Black and P. Rogaway. Ciphers with arbitrary finite domains. In Proc. of CT-RSA, volume 2271 of LNCS, pages 114--130. Springer-Verlag, 2002. Google Scholar
- M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. In Proc. of the FOCS '95, 1995.Google Scholar
- D. Boneh, G. di Crescenzo, R. Ostrovsky, and G. Persiano. Public key encryption with key-word search. In EUROCRYPT'04, 2004.Google ScholarCross Ref
- I. Clarke, O. Sandberg, B. Wiley, and T. W. Hong. Freenet: a distributed anonymous information storage and retrieval system. In International workshop on Designing privacy enhancing technologies, pages 46--66, New York, NY, USA, 2001. Springer-Verlag New York, Inc. Google ScholarDigital Library
- B. Cooper and H. Garcia-Molina. Peer-to-peer data trading to preserve information. ACM ToIS, 20(2):133--170, 2002. Google ScholarDigital Library
- R. Curtmola, O. Khan, R. Burns, and G. Ateniese. Mr. pdp: Multiple-replica provable data possession. In Proc. of The 28th IEEE International Conference on Distributed Computing Systems (ICDCS'08), 2008, to appear. Google ScholarDigital Library
- Y. Deswarte, J.-J. Quisquater, and A. Saidane. Remote integrity checking. In Proc. of Conference on Integrity and Internal Control in Information Systems (IICIS'03), November 2003.Google Scholar
- P. Devanbu, M. Gertz, C. Martel, and S. Stubblebine. Authentic third-party data publication. In IFIP DBSec'03, also in Journal of Computer Security, Vol. 11, No. 3, pages 291--314, 2003, 2003. Google ScholarDigital Library
- D. L. G. Filho and P. S. L. M. Baretto. Demonstrating data possession and uncheatable data transfer. IACR ePrint archive, 2006. Report 2006/150, http://eprint.iacr.org/2006/150.Google Scholar
- J. F. Gantz, D. Reinsel, C. Chute, W. Schlichting, J. McArthur, S. Minton, I. Xheneti, A. Toncheva, and A. Manfrediz. The expanding digital universe: A forecast of worldwide information growth through 2010. IDC white paper---sponsored by EMC. Technical report, March 2007. http://www.emc.com/about/destination/digital_universe/.Google Scholar
- P. Golle, S. Jarecki, and I. Mironov. Cryptographic primitives enforcing communication and storage complexity. In Financial Cryptography, pages 120--135, 2002.Google Scholar
- P. Golle, J. Staddon, and B. Waters. Secure conjunctive keyword search over encrypted data. In ACNS'04, 2004.Google ScholarCross Ref
- G. R. Goodson, J. J. Wylie, G. R. Ganger, and M. K. Reiter. Efficient byzantine-tolerant erasure-coded storage. In DSN '04: Proceedings of the 2004 International Conference on Dependable Systems and Networks, page 135, Washington, DC, USA, 2004. IEEE Computer Society. Google ScholarDigital Library
- H. Hacigümüs, B. Iyer, C. Li, and S. Mehrotra. Executing sql over encrypted data in the database-service-provider model. In ACM SIGMOD'02, 2002. Google ScholarDigital Library
- A. Juels and B. Kaliski. PORs: Proofs of retrievability for large files. In ACM CCS'07, Full paper available on e-print (2007/243), 2007. Google ScholarDigital Library
- A. Juels and B. S. Kaliski. http://www.rsa.com/rsalabs/staff/bios/ajuels/presentations/Proofs_of_Retrievability_CCS.ppt.Google Scholar
- J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. Oceanstore: an architecture for global-scale persistent storage. SIGPLAN Not., 35(11):190--201, 2000. Google ScholarDigital Library
- M. Lillibridge, S. Elnikety, A. Birrell, M. Burrows, and M. Isard. A cooperative internet backup scheme. In USENIX'03, 2003. Google ScholarDigital Library
- E. Mykletun, M. Narasimha, and G. Tsudik. Authentication and integrity in outsourced databases. In ISOC NDSS'04, 2004.Google Scholar
- M. Naor and G. N. Rothblum. The complexity of online memory checking. In Proc. of FOCS, 2005. Full version appears as ePrint Archive Report 2006/091. Google ScholarDigital Library
- P. Rogaway, M. Bellare, and J. Black. OCB: A block-cipher mode of operation for efficient authenticated encryption. ACM TISSEC, 6(3), 2003. Google ScholarDigital Library
- T. S. J. Schwarz and E. L. Miller. Store, forget, and check: Using algebraic signatures to check remotely administered storage. In Proceedings of ICDCS '06. IEEE Computer Society, 2006. Google ScholarDigital Library
- 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.Google Scholar
- H. Shacham and B. Waters. Compact proofs of retrievability. Cryptology ePrint archive, June 2008. Report 2008/073.Google Scholar
- M. Shah, R. Swaminathan, and M. Baker. Privacy-preserving audit and extraction of digital contents. Cryptology ePrint archive, April 2008. Report 2008/186.Google Scholar
- D. Song, D. Wagner, and A. Perrig. Practical techniques for searches on encrypted data. In IEEE S&P'00, 2000. Google ScholarDigital Library
- M. Waldman and D. Mazières. TANGLER: a censorship-resistant publishing system based on document entanglements. In ACM CCS'01, 2001. Google ScholarDigital Library
- M. Waldman, A. Rubin, and L. Cranor. PUBLIUS: a robust, tamper-evident, censorship-resistant web publishing system. In USENIX SEC'00, 2000. Google ScholarDigital Library
Index Terms
- Scalable and efficient provable data possession
Recommendations
Dynamic Provable Data Possession
As storage-outsourcing services and resource-sharing networks have become popular, the problem of efficiently proving the integrity of data stored at untrusted servers has received increased attention. In the Provable Data Possession (PDP) model, the ...
Remote data checking using provable data possession
We introduce a model for provable data possession (PDP) that can be used for remote data checking: A client that has stored data at an untrusted server can verify that the server possesses the original data without retrieving it. The model generates ...
Dynamic provable data possession
CCS '09: Proceedings of the 16th ACM conference on Computer and communications securityWe consider the problem of efficiently proving the integrity of data stored at untrusted servers. In the provable data possession (PDP) model, the client preprocesses the data and then sends it to an untrusted server for storage, while keeping a small ...
Comments