Article

Provable data possession at untrusted stores

Authors:

Giuseppe Ateniese,

Joseph Herring,

Zachary Peterson,

Dawn SongAuthors Info & Claims

CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

Pages 598 - 609

https://doi.org/10.1145/1315245.1315318

Published: 28 October 2007 Publication History

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.

Digital Library

[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]

M. Bellare and O. Goldreich. On defining proofs of knowledge. In Proc. of CRYPTO '92, pages 390--420, 1992.

Digital Library

[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]

M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proc. of CCS'93, pages 62--73. ACM, 1993.

Digital Library

[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.

Digital Library

[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]

J. Black and P. Rogaway. Ciphers with arbitrary finite domains. In Proc. of CT-RSA, pages 114--130, 2002.

Digital Library

[12]

M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. Checking the correctness of memories. In Proc. of FOCS '95.

Digital Library

[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.

Digital Library

[14]

I. Damgaård. Towards practical public key systems secure against chosen ciphertext attacks. In J. Feigenbaum, editor, CRYPTO91, volume 576, pages 445--456. Springer, 1992.

Digital Library

[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.

Digital Library

[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]

A. Fiat. Batch RSA. In GBrassard, editor, Proc. CRYPTO 89, pages 175--185. Springer-Verlag, 1990.

Digital Library

[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.

Digital Library

[21]

S. Hada and T. Tanaka. On the existence of 3-round zero-knowledge protocols. In Proc. of CRYPTO '98, volume 1462 of LNCS, pages 408--423. Springer, 1998.

Digital Library

[22]

L. Harn. Batch verifying multiple RSA digital signatures. Electronics Letters, 34(12):1219--1220, 1998.

[23]

R. Hasan, W. Yurcik, and S. Myagmar. The evolution of storage server providers: Techniques and challenges to outsourcing storage. In Proc. of the Workshop on Storage Security and Survivability, 2005.

Digital Library

[24]

R. Johnson, D. Molnar, D. Song, and D. Wagner. Homomorphic signature schemes. In Proc. of CT-RSA, volume 2271 of LNCS, pages 244--262. Springer, 2002.

Digital Library

[25]

A. Juels and B. S. Kaliski. PORs: Proofs of retrievability for large files. Cryptology ePrint archive, June 2007. Report 2007/243.

[26]

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

Digital Library

[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.

Digital Library

[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]

J. Kubiatowicz, D. Bindel, Y. Chen, 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. In Proc. of ACM ASPLOS '00. ACM, November 2000.

Digital Library

[30]

J. Li, M. Krohn, D. Mazières, and D. Shasha. Secure untrusted data repository (SUNDR). In Proc. of OSDI, 2004.

Digital Library

[31]

U. Maheshwari, R. Vingralek, and W. Shapiro. How to build a trusted database system on untrusted storage. In Proc. of OSDI, 2000.

Digital Library

[32]

P. Maniatis, M. Roussopoulos, T. Giuli, D. Rosenthal, M. Baker, and Y. Muliadi. The LOCKSS peer-to-peer digital preservation system. ACM Transactions on Computing Systems, 23(1):2--50, 2005.

Digital Library

[33]

S. Micali, K. Ohta, and L. Reyzin. Accountable-subgroup multisignatures: extended abstract. In Proc of ACM CCS '01.

Digital Library

[34]

G. L. Miller. Riemann's hypothesis and tests for primality. JCSS, 13(3):300--317, 1976.

Digital Library

[35]

A. A. Muthitacharoen, R. Morris., T. M. Gil, and B. Chen. Ivy: A read/write peer-to-peer file system. In Proc. of OSDI '02.

Digital Library

[36]

E. Mykletun, M. Narasimha, and G. Tsudik. Authentication and integrity in outsourced databases. In Proc. of NDSS '04.

[37]

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.

Digital Library

[38]

T. Okamoto. A digital multisignature schema using bijective public-key cryptosystems. ACM Transactions on Computer Systems, 6(4):432--441, 1988.

Digital Library

[39]

A. Oprea, M. K. Reiter, and K. Yang. Space-efficient block storage integrity. In Proc. of NDSS '05, 2005.

[40]

T. S. J. Schwarz and E. L. Miller. Store, forget, and check: Using algebraic signatures to check remotely administered storage. In Proc. of ICDCS '06, 2006.

Digital Library

[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]

M. Shah, M. Baker, J. C. Mogul, and R. Swaminathan. Auditing to keep online storage services honest. In Proc. of HotOS XI. Usenix, 2007.

Digital Library

[43]

A. Shamir. On the generation of cryptographically strong pseudorandom sequences. ACM Trans. Comput. Syst., 1(1):38--44, 1983.

Digital Library

[44]

D. Thompson and J. Best. The future of magnetic data storage technology. IBM Journal Research and Development, 44(3):311--319, May 2000.

Digital Library

[45]

M. Waldman and D. Mazières. Tangler: a censorship-resistant publishing system based on document entanglements. In Proc. of CCS, 2001.

Digital Library

[46]

A. Y. Yumerefendi and J. Chase. Strong accountability for network storage. In Proc. of FAST, 2007.

Digital Library

Cited By

Wang FLin CYuan M(2025)Revisiting “online/offline provable data possession” schemesComputer Standards & Interfaces10.1016/j.csi.2024.10389891(103898)Online publication date: Jan-2025
https://doi.org/10.1016/j.csi.2024.103898
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
Mageshwari MPrabakar DAnitha SVasim Babu M(2024)Dynamic Evaluation Service for Safe Cloud Retention With Protection of Privacy and Reduction of Cyber Security AttacksEnhancing Security in Public Spaces Through Generative Adversarial Networks (GANs)10.4018/979-8-3693-3597-0.ch010(138-151)Online publication date: 17-May-2024
https://doi.org/10.4018/979-8-3693-3597-0.ch010
Show More Cited By

Index Terms

Provable data possession at untrusted stores

Recommendations

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 security

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 ...
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 ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '07: Proceedings of the 14th ACM conference on Computer and communications security

October 2007

628 pages

ISBN:9781595937032

DOI:10.1145/1315245

General Chair:
Peng Ning
NC State University, USA
,
Program Chairs:
Sabrina De Capitani di Vimercati
University of Milan, Italy
,
Paul Syverson
Naval Research Laboratory, USA

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 October 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CCS07

Sponsor:

CCS07: 14th ACM Conference on Computer and Communications Security 2007

November 2 - October 31, 2007

Virginia, Alexandria, USA

Acceptance Rates

CCS '07 Paper Acceptance Rate 55 of 302 submissions, 18%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1,385
Total Citations
View Citations
5,181
Total Downloads

Downloads (Last 12 months)320
Downloads (Last 6 weeks)29

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang FLin CYuan M(2025)Revisiting “online/offline provable data possession” schemesComputer Standards & Interfaces10.1016/j.csi.2024.10389891(103898)Online publication date: Jan-2025
https://doi.org/10.1016/j.csi.2024.103898
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
Mageshwari MPrabakar DAnitha SVasim Babu M(2024)Dynamic Evaluation Service for Safe Cloud Retention With Protection of Privacy and Reduction of Cyber Security AttacksEnhancing Security in Public Spaces Through Generative Adversarial Networks (GANs)10.4018/979-8-3693-3597-0.ch010(138-151)Online publication date: 17-May-2024
https://doi.org/10.4018/979-8-3693-3597-0.ch010
Chang ZWu JLiang HWang YWang YXiong X(2024)A Review of Power System False Data Attack Detection Technology Based on Big DataInformation10.3390/info1508043915:8(439)Online publication date: 28-Jul-2024
https://doi.org/10.3390/info15080439
SUN YYANG FCHEN XDU XLIN W(2024)Research progress of verifiable technologies for outsourcing servicesSCIENTIA SINICA Informationis10.1360/SSI-2022-036054:3(514)Online publication date: 6-Mar-2024
https://doi.org/10.1360/SSI-2022-0360
Wang YYou WZhang YYe AXu L(2024)Cloud EMRs auditing with decentralized (t, n)-threshold ownership transferCybersecurity10.1186/s42400-024-00246-47:1Online publication date: 18-Sep-2024
https://doi.org/10.1186/s42400-024-00246-4
Correia CPrates RFonseca LCorreia MRodrigues L(2024)PoTR: Accurate and Efficient Proof of Timely-Retrievability for Storage SystemsFormal Aspects of Computing10.1145/3685935Online publication date: 2-Aug-2024
https://dl.acm.org/doi/10.1145/3685935
Zhao JYang ZLi JLee P(2024)Encrypted Data Reduction: Removing Redundancy from Encrypted Data in Outsourced StorageACM Transactions on Storage10.1145/368527820:4(1-30)Online publication date: 29-Jul-2024
https://dl.acm.org/doi/10.1145/3685278
Zhao YQu YXiang YUddin MPeng DGao L(2024)A Comprehensive Survey on Edge Data Integrity Verification: Fundamentals and Future TrendsACM Computing Surveys10.1145/368027757:1(1-34)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3680277
Cohen BHu APatino DCoffman J(2024)This Is Going on Your Permanent Record: A Legal Analysis of Educational Data in the CloudACM Journal on Responsible Computing10.1145/36752301:3(1-27)Online publication date: 4-Jul-2024
https://dl.acm.org/doi/10.1145/3675230
Show More Cited By

View Options

Get Access

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