Paper 2022/1417

Efficient Dynamic Proof of Retrievability for Cold Storage

Tung Le, Virginia Tech
Pengzhi Huang, Cornell University
Attila A. Yavuz, University of South Florida
Elaine Shi, Carnegie Mellon University
Thang Hoang, Virginia Tech

Storage-as-a-service (STaaS) permits the client to outsource her data to the cloud thereby, reducing data management and maintenance costs. However, STaaS also brings significant data integrity and soundness concerns since the storage provider might not keep the client data intact and retrievable all the time (e.g., cost saving via deletions). Proof of Retrievability (PoR) can validate the integrity and retrievability of remote data effectively. This technique can be useful for regular audits to monitor data compromises, as well as to comply with standard data regulations. In particular, cold storage applications (e.g., MS Azure, Amazon Glacier) require regular and frequent audits but with less frequent data modification. Yet, despite their merits, existing PoR techniques generally focus on other metrics (e.g., low storage, fast update, metadata privacy) but not audit efficiency (e.g., low audit time, small proof size). Hence, there is a need to develop new PoR techniques that achieve efficient data audit while preserving update and retrieval performance. In this paper, we propose Porla, a new PoR framework that permits efficient data audit, update, and retrieval functionalities simultaneously. Porla permits data audit in both private and public settings, each of which features asymptotically (and concretely) smaller audit-proof size and lower audit time than all the prior works while retaining the same asymptotic data update overhead. Porla achieves all these properties by composing erasure codes with verifiable computation techniques which, to our knowledge, is a new approach to PoR design. We address several challenges that arise in such a composition by creating a new homomorphic authenticated commitment scheme, which can be of independent interest. We fully implemented Porla and evaluated its performance on commodity cloud (i.e., Amazon EC2) under various settings. Experimental results demonstrated that Porla achieves two to four orders of magnitude smaller audit proof size with 4× – 1,800× lower audit time than all prior schemes in both private and public audit settings at the cost of only 2× – 3× slower update.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. NDSS 2023
proof of retrievability commitment schemes data audit error correction code cloud storage
Contact author(s)
tungle @ vt edu
ph448 @ cornell edu
attilaayavuz @ usf edu
runting @ gmail com
thanghoang @ vt edu
2022-10-24: approved
2022-10-18: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Tung Le and Pengzhi Huang and Attila A. Yavuz and Elaine Shi and Thang Hoang},
      title = {Efficient Dynamic Proof of Retrievability for Cold Storage},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1417},
      year = {2022},
      doi = {10.14722/ndss.2023.23307},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.