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

Article

Proofs of Storage from Homomorphic Identification Protocols

Authors:

Giuseppe Ateniese,

Jonathan KatzAuthors Info & Claims

ASIACRYPT '09: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology

Pages 319 - 333

https://doi.org/10.1007/978-3-642-10366-7_19

Published: 02 December 2009 Publication History

Abstract

Proofs of storage (PoS) are interactive protocols allowing a client to verify that a server faithfully stores a file. Previous work has shown that proofs of storage can be constructed from any homomorphic linear authenticator (HLA). The latter, roughly speaking, are signature/message authentication schemes where `tags' on multiple messages can be homomorphically combined to yield a `tag' on any linear combination of these messages.

We provide a framework for building public-key HLAs from any identification protocol satisfying certain homomorphic properties. We then show how to turn any public-key HLA into a publicly-verifiable PoS with communication complexity independent of the file length and supporting an unbounded number of verifications. We illustrate the use of our transformations by applying them to a variant of an identification protocol by Shoup, thus obtaining the first unbounded-use PoS based on factoring (in the random oracle model).

References

[1]

Ateniese, G., Burns, R., Curtmola, R., Herring, J., Kissner, L., Peterson, Z., Song, D.: Provable data possession at untrusted stores. In: ACMConference on Computer and Communications Security. ACM, New York (2007)

Digital Library

[2]

Ateniese, G., Di Pietro, R., Mancini, L.V., Tsudik, G.: Scalable and efficient provable data possession. In: Proc. 4th Intl. Conf. on Security and Privacy in Communication Netowrks (SecureComm 2008), pp. 1-10. ACM, New York (2008)

Digital Library

[3]

Bellare, M., Goldreich, O.: On defining proofs of knowledge. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 390-420. Springer, Heidelberg (1993)

Digital Library

[4]

Bowers, K., Juels, A., Oprea, A.: Proofs of retrievability: Theory and implementation. Technical Report 2008/175, Cryptology ePrint Archive (2008)

[5]

Dodis, Y., Vadhan, S., Wichs, D.: Proofs of retrievability via hardness amplification. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 109-127. Springer, Heidelberg (2009)

Digital Library

[6]

Erway, C., Papamanthou, C., Kupcu, A., Tamassia, R.: Dynamic provable data possession. In: ACM Conf. on Computer and Communications Security (to appear, 2009). Available as Cryptology ePrint Archive, Report 2008/432

Digital Library

[7]

Feige, U., Fiat, A., Shamir, A.: Zero knowledge proofs of identity. J. Cryptology 1(2), 77-94 (1988)

Digital Library

[8]

Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptology 9(3), 167-190 (1996)

[9]

Groth, J.: A verifiable secret shuffle of homomorphic encryptions. Technical Report 2005/246, IACR ePrint Cryptography Archive (2005)

[10]

Guillou, L., Quisquater, J.-J.: A practical zero-knowledge protocol fitted to security microprocessor minimizing both transmission and memory. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 123-128. Springer, Heidelberg (1988)

Digital Library

[11]

Juels, A., Kaliski, B.: PORs: Proofs of retrievability for large files. In: ACM Conference on Computer and Communications Security. ACM, New York (2007)

Digital Library

[12]

Lindell, Y.: Parallel coin-tossing and constant-round secure two-party computation. J. Cryptology 16(3), 143-184 (2003)

[13]

Naor, M., Rothblum, G.: The complexity of online memory checking. In: IEEE Symposium on Foundations of Computer Science, pp. 573-584. IEEE Computer Society, Los Alamitos (2005)

Digital Library

[14]

Shacham, H., Waters, B.: Compact proofs of retrievability. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 90-107. Springer, Heidelberg (2008), Full version http://eprint.iacr.org

Digital Library

[15]

Shoup, V.: On the security of a practical identification scheme. J. Cryptology 12(4), 247-260 (1999)

Cited By

Li YSusilo WGuo F(2024)Public Auditing with Aggregated Tags for Multiple UsersData Security and Privacy Protection10.1007/978-981-97-8546-9_7(122-139)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8546-9_7
Nygaard RMeling HOlsen JHong JLanperne MPark JCerny TShahriar H(2023)Cost-effective Data Upkeep in Decentralized Storage SystemsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577728(165-173)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577728
Li ZAhmad MJin YHaipei WZhantu L(2023)Unleashing Trustworthy Cloud Storage: Harnessing Blockchain for Cloud Data Integrity VerificationAdvances in Visual Informatics10.1007/978-981-99-7339-2_37(443-452)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-7339-2_37
Show More Cited By

Recommendations

Protocols and security proofs for data authentication
Proofs of retrievability from linearly homomorphic structure-preserving signatures

Proofs of retrievability PoR enables clients to outsource huge amount of data to cloud servers, and provides an efficient audit protocol, which can be employed to check that all the data is being maintained properly and can be retrieved from the server. ...
Group-oriented Proofs of Storage
ASIA CCS '15: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security

We introduce and formalize the notion of group-oriented proofs of storage (GPoS). In GPoS, each file owner, after being authorized as a member by a group manager, can outsource files to a group storage account maintained by an untrusted party, for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ASIACRYPT '09: Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology

December 2009

720 pages

ISBN:9783642103650

Editor:
Mitsuru Matsui
Information Technology R&D Center, Mitsubishi Electric Corporation, Kamakura, Kanagawa, Japan 247-8501

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 02 December 2009

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li YSusilo WGuo F(2024)Public Auditing with Aggregated Tags for Multiple UsersData Security and Privacy Protection10.1007/978-981-97-8546-9_7(122-139)Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1007/978-981-97-8546-9_7
Nygaard RMeling HOlsen JHong JLanperne MPark JCerny TShahriar H(2023)Cost-effective Data Upkeep in Decentralized Storage SystemsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577728(165-173)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577728
Li ZAhmad MJin YHaipei WZhantu L(2023)Unleashing Trustworthy Cloud Storage: Harnessing Blockchain for Cloud Data Integrity VerificationAdvances in Visual Informatics10.1007/978-981-99-7339-2_37(443-452)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1007/978-981-99-7339-2_37
Lin CXue RHuang X(2021)Linearly Homomorphic Signatures with Designated CombinerProvable and Practical Security10.1007/978-3-030-90402-9_18(327-345)Online publication date: 5-Nov-2021
https://dl.acm.org/doi/10.1007/978-3-030-90402-9_18
Etemad MKüpçü A(2020)Generic Dynamic Data Outsourcing Framework for Integrity VerificationACM Computing Surveys10.1145/336599853:1(1-32)Online publication date: 6-Feb-2020
https://dl.acm.org/doi/10.1145/3365998
Long MPeng FLi Y(2019)Dynamic Provable Data Possession of Multiple Copies in Cloud Storage Based on Full-Node of AVL TreeInternational Journal of Digital Crime and Forensics10.4018/IJDCF.201901011011:1(126-137)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.4018/IJDCF.2019010110
Li YYu YMin GSusilo WNi JChoo K(2019)Fuzzy Identity-Based Data Integrity Auditing for Reliable Cloud Storage SystemsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.266221616:1(72-83)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1109/TDSC.2017.2662216
Luo FWang FWang KChen K(2019)A more efficient leveled strongly-unforgeable fully homomorphic signature schemeInformation Sciences: an International Journal10.1016/j.ins.2018.12.025480:C(70-89)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1016/j.ins.2018.12.025
Wu GMu YSusilo WGuo FZhang F(2019)Privacy-Preserving Certificateless Cloud Auditing with Multiple UsersWireless Personal Communications: An International Journal10.1007/s11277-019-06208-1106:3(1161-1182)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s11277-019-06208-1
Wang TYang BLiu HYu YQiu GXia Z(2019)An alternative approach to public cloud data auditing supporting data dynamicsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3155-423:13(4939-4953)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00500-018-3155-4
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents