More Web Proxy on the site http://driver.im/

research-article

Dynamic provable data possession

Authors:

Alptekin Küpçü,

Charalampos Papamanthou,

Roberto TamassiaAuthors Info & Claims

CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

Pages 213 - 222

https://doi.org/10.1145/1653662.1653688

Published: 09 November 2009 Publication History

Abstract

We 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 amount of meta-data. The client later asks the server to prove that the stored data has not been tampered with or deleted (without downloading the actual data). However, the original PDP scheme applies only to static (or append-only) files.

We present a definitional framework and efficient constructions for dynamic provable data possession (DPDP), which extends the PDP model to support provable updates to stored data. We use a new version of authenticated dictionaries based on rank information. The price of dynamic updates is a performance change from O(1) to O(logn) (or O(n^εlog n), for a file consisting of n blocks, while maintaining the same (or better, respectively) probability of misbehavior detection. Our experiments show that this slowdown is very low in practice (e.g. 415KB proof size and 30ms computational overhead for a 1GB file). We also show how to apply our DPDP scheme to outsourced file systems and version control systems (e.g. CVS).

References

[1]

A. Anagnostopoulos, M. Goodrich, and R. Tamassia. Persistent authenticated dictionaries and their applications. In ISC, pp. 379--393, 2001.

Digital Library

[2]

G. Ateniese, R. Burns, R. Curtmola, J. Herring, L. Kissner, Z. Peterson, and D. Song. Provable data possession at untrusted stores. In CCS, pp. 598--609, 2007.

Digital Library

[3]

G. Ateniese, R. D. Pietro, L. V. Mancini, and G. Tsudik. Scalable and efficient provable data possession. In SecureComm, pp. 1--10, 2008.

Digital Library

[4]

GM. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. Algorithmica, 12(2):225--244, 1994.

Digital Library

[5]

D. Boneh, B. Lynn, and H. Shacham. Short signatures from the weil pairing. In ASIACRYPT, pp. 514--532, 2001.

Digital Library

[6]

D. E. Clarke, S. Devadas, M. van Dijk, B. Gassend, and G. E. Suh. Incremental multiset hash functions and their application to memory integrity checking. In ASIACRYPT, pp. 188--207, 2003.

[7]

Y. Dodis, S. Vadhan, and D. Wichs. Proofs of retrievability via hardness amplification. In TCC, pp. 109--127, 2009.

Digital Library

[8]

C. Dwork, M. Naor, G. N. Rothblum, and V. Vaikuntanathan. How efficient can memory checking be? In TCC, pp. 503--520, 2009.

Digital Library

[9]

C. C. Erway, A. Küpçü, C. Papamanthou, and R. Tamassia. Dynamic provable data possession. Cryptology ePrint 2008/432. http://eprint.iacr.org/2008/432.pdf.

[10]

D. L. Gazzoni and P. S. L. M. Barreto. Demonstrating data possession and uncheatable data transfer. Cryptology ePrint Archive, Report 2006/150, 2006.

[11]

M. T. Goodrich, C. Papamanthou, R. Tamassia, and N. Triandopoulos. Athos: Efficient authentication of outsourced file systems. In ISC, pp. 80--96, 2008.

Digital Library

[12]

M. T. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In DISCEX II, pp. 68--82, 2001.

[13]

A. Juels and B. S. Kaliski. PORs: Proofs of retrievability for large files. In CCS, pp. 584--597, 2007.

Digital Library

[14]

M. Kallahalla, E. Riedel, R. Swaminathan, Q. Wang, and K. Fu. Plutus: Scalable secure file sharing on untrusted storage. In FAST, pp. 29--42, 2003.

Digital Library

[15]

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.

Digital Library

[16]

F. Li, M. Hadjieleftheriou, G. Kollios, and L. Reyzin. Dynamic authenticated index structures for outsourced databases. In SIGMOD, pp. 121--132, 2006.

Digital Library

[17]

J. Li, M. Krohn, D. Mazieres, and D. Shasha. Secure untrusted data repository (SUNDR). In OSDI, pp. 121--136, 2004.

Digital Library

[18]

U. Maheshwari, R. Vingralek, and W. Shapiro. How to build a trusted database system on untrusted storage. In OSDI, pp. 10--26, 2000.

Digital Library

[19]

A. Muthitacharoen, R. Morris, T. Gil, and B. Chen. Ivy: A read/write peer-to-peer file system. In OSDI, pp. 31--44, 2002.

Digital Library

[20]

M. Naor and K. Nissim. Certificate revocation and certificate update. In USENIX Security, pp. 17--17, 1998.

Digital Library

[21]

M. Naor and G. N. Rothblum. The complexity of online memory checking. J. ACM., 56(1):1--46, 2009.

Digital Library

[22]

A. Oprea, M. Reiter, and K. Yang. Space-efficient block storage integrity. In NDSS, pp. 17--28, 2005.

[23]

J. Ousterhout. Tcl/tk. http://www.tcl.tk/.

[24]

C. Papamanthou and R. Tamassia. Time and space efficient algorithms for two-party authenticated data structures. In ICICS, pp. 1--15, 2007.

Digital Library

[25]

C. Papamanthou, R. Tamassia, and N. Triandopoulos. Authenticated hash tables. In CCS, pp. 437--448, 2008.

Digital Library

[26]

W. Pugh. Skip lists: A probabilistic alternative to balanced trees. Commun. ACM, 33(6):668--676, 1990.

Digital Library

[27]

Samba. Samba.org CVS repository. http://cvs.samba.org/cgi-bin/cvsweb/.

[28]

T. Schwarz and E. Miller. Store, forget, and check: Using algebraic signatures to check remotely administered storage. In ICDCS, pp. 12, 2006.

Digital Library

[29]

F. Sebe, A. Martinez-Balleste, Y. Deswarte, J. Domingo-Ferre, and J.-J. Quisquater. Time-bounded remote file integrity checking. Technical Report 04429, LAAS, July 2004.

[30]

H. Shacham and B. Waters. Compact proofs of retrievability. In ASIACRYPT, pp. 90--107, 2008.

Digital Library

[31]

R. Tamassia. Authenticated data structures. In ESA, pp. 2--5, 2003.

[32]

R. Tamassia and N. Triandopoulos. Computational bounds on hierarchical data processing with applications to information security. In ICALP, pp. 153--165, 2005.

Digital Library

Cited By

Pranav Pujari Ritesh Pawar Vadnaya Wable Ghanshyam Ramole Narendra Joshi (2024)Certificateless Public Integrity Checking of Group Shared Data in Cloud StorageInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-22482(550-556)Online publication date: 28-Nov-2024
https://doi.org/10.48175/IJARSCT-22482
Ms. Aishwarya S. Khutwad Mr. Ajay P. Ganore Mr. Shubham B. Ganore Mr. Vishal P. Shinde (2024)Secure Cloud Storage with Deduplication TechniqueInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-16937(204-209)Online publication date: 5-Apr-2024
https://doi.org/10.48175/IJARSCT-16937
Wang HWan ZHe DYu J(2024)Synchronous Blockchain-Based Distributed Provable Data Possession With Forward-SecurityIEEE Transactions on Services Computing10.1109/TSC.2023.332402317:3(1227-1238)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3324023
Show More Cited By

Index Terms

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 ...
Scalable and efficient provable data possession
SecureComm '08: Proceedings of the 4th international conference on Security and privacy in communication netowrks

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 ...
Fair and dynamic proofs of retrievability
CODASPY '11: Proceedings of the first ACM conference on Data and application security and privacy

Cloud computing is getting increasingly popular, but has yet to be widely adopted arguably because there are many security and privacy problems that have not been adequately addressed. A specific problem encountered in the context of cloud storage, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

November 2009

664 pages

ISBN:9781605588940

DOI:10.1145/1653662

General Chair:
Ehab Al-Shaer
University of North Carolina, Charlotte, USA
,
Program Chairs:
Somesh Jha
University of Wisconsin, USA
,
Angelos D. Keromytis
Columbia University, USA and Symantec Research Labs Europe, France

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 November 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '09

Sponsor:

SIGSAC

CCS '09: 16th ACM Conference on Computer and Communications Security 2009

November 9 - 13, 2009

Illinois, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

552
Total Citations
View Citations
2,064
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pranav Pujari Ritesh Pawar Vadnaya Wable Ghanshyam Ramole Narendra Joshi (2024)Certificateless Public Integrity Checking of Group Shared Data in Cloud StorageInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-22482(550-556)Online publication date: 28-Nov-2024
https://doi.org/10.48175/IJARSCT-22482
Ms. Aishwarya S. Khutwad Mr. Ajay P. Ganore Mr. Shubham B. Ganore Mr. Vishal P. Shinde (2024)Secure Cloud Storage with Deduplication TechniqueInternational Journal of Advanced Research in Science, Communication and Technology10.48175/IJARSCT-16937(204-209)Online publication date: 5-Apr-2024
https://doi.org/10.48175/IJARSCT-16937
Wang HWan ZHe DYu J(2024)Synchronous Blockchain-Based Distributed Provable Data Possession With Forward-SecurityIEEE Transactions on Services Computing10.1109/TSC.2023.332402317:3(1227-1238)Online publication date: May-2024
https://doi.org/10.1109/TSC.2023.3324023
Du YZhou AWang C(2024)DWare: Cost-Efficient Decentralized Storage With Adaptive MiddlewareIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.345965019(8529-8543)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3459650
Cui HWan ZGao RWang H(2024)Outsourced Privately Verifiable Proofs of Retrievability via BlockchainIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.328521821:4(1501-1514)Online publication date: Jul-2024
https://doi.org/10.1109/TDSC.2023.3285218
Cui HWan ZZhaolu TWang HMiyaji A(2024)Pay-Per-Proof: Decentralized Outsourced Multi-User PoR for Cloud Storage Payment Using BlockchainIEEE Transactions on Cloud Computing10.1109/TCC.2023.334371012:1(130-144)Online publication date: Jan-2024
https://doi.org/10.1109/TCC.2023.3343710
Islam TBappy FUl Haque Shifat MAhmad FHasan KZaman T(2024)An Efficient and Scalable Auditing Scheme for Cloud Data Storage Using an Enhanced B-TreeICC 2024 - IEEE International Conference on Communications10.1109/ICC51166.2024.10622517(4590-4595)Online publication date: 9-Jun-2024
https://doi.org/10.1109/ICC51166.2024.10622517
Yi CZhang HSun WDing J(2024)DBT-PDP: Provable data possession with outsourced data batch transfer based on blockchainHigh-Confidence Computing10.1016/j.hcc.2023.1001524:2(100152)Online publication date: Jun-2024
https://doi.org/10.1016/j.hcc.2023.100152
Farooq MGhazali O(2024)Remote Public Data Auditing to Secure Cloud StorageComputing and Informatics10.1007/978-981-99-9589-9_6(70-79)Online publication date: 26-Jan-2024
https://doi.org/10.1007/978-981-99-9589-9_6
Pragathy VYamuna Devi L(2024)Enhanced Dynamic Remote Data Possession Checking Protocol with Unlimited Number of Verifications and Public Verifiability for Ensuring Cloud Data IntegrityAdvances in Data-Driven Computing and Intelligent Systems10.1007/978-981-99-9531-8_15(181-199)Online publication date: 11-Apr-2024
https://doi.org/10.1007/978-981-99-9531-8_15
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents