Efficient Dynamic Proof of Retrievability for Cold Storage

Abstract

to unwanted accidents (e.g., hardware failure) or adversarial behaviors.For instance, the adversary may strategically omit some important data update, or delete certain parts of the data that are rarely accessed to reduce storage overhead and monetary maintenance costs.Under a standard Service Level Agreement (SLA), a reliable and trustworthy storage provider is expected to comply with standard data regulations (e.g., [35], [45], [39]) by performing a regular audit to ensure persistent data integrity and freshness.Audit-proof archiving [2] is one of the best practices for secure digital data storage that generally maintains sensitive information (e.g., personal, health).A fine-grained audit on a regular basis is necessary to continuously monitor the system activities against potential threats [33].In particular, cold storage and archival applications (e.g., Amazon Glacier [1], MS Azure Archive [3], or Blob [13]) maintain a large amount of archival data that is for long-term maintenance [14], [10].In such applications, the archives are rarely updated but must be periodically audited to ensure their availability and trustworthiness.Both the size of the data and the number of audit logs grow significantly over time.Hence, it is critical that the size of cryptographic audit tags is small to avoid storage bottlenecks in cold storage and digital archival systems. Several cryptographic techniques have been developed[11], [31] to permit effective data integrity audit.Provable Data Possession (PDP) [11] allows a client to check whether her data is kept intact by the storage server.Despite its merits, PDP only ensures the integrity of most of the data, but not all.By deleting a small portion of the data, the adversarial server can still bypass the audit with a high probability.Proof of Retrievability (PoR) [31] achieves a stronger security notion in the sense that the audit can provably tell whether all the data is intact and retrievable or not.While preliminary PoR schemes are static (e.g., [40], [17], [31]), recent Dynamic PoR (DPoR) constructions (e.g., [7], [15], [20], [41], [43]) have enabled data updatability and auditability simultaneously.Most proposed DPoR schemes rely on coding theory and cryptographic techniques as the main building blocks such as error correction code (ECC) [20], [41], [43], Oblivious RAM (ORAM) [20], and verifiable computation [7], [15].Each of the proposed DPoR schemes to date features unique properties with special characteristics (e.g., strong privacy, update efficiency, low storage).However, most of them are not ideal for audit-intensive use cases.Specifically, apart from the auditability, can also hide data access patterns (e.g., read/write); however, it incurs significantly high communication overhead during an audit.Shi et al. proposed a DPoR scheme based on a locally Abstract-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 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×-18000× lower audit time than all prior schemes in both private and public audit settings at the cost of only 2×-3× slower update.

Topics & Concepts