Provable data deletion from efficient data integrity auditing and insertion in cloud storage

• We design a novel authentication data structure, namely, number-rank-based Merkle hash tree (NR-MHT), in which every leaf node can maintain plenty of data blocks. • As a result, the height of NR-MHT will not indefinitely increase with the number of data blocks. • Hence, the height of NR-MHT will be further controlled within an acceptable range by changing the number of data blocks that stored in every leaf node. • Meanwhile, the number of data blocks stored in each leaf node is variable, thus NR-MHT can support data dynamic operations, which is quite suitable for dynamic outsourced data storage scenarios. • We adopt NR-MHT to design a new provable outsourced data deletion scheme, which can simultaneously achieve efficient data integrity auditing and dynamic data insertion in cloud storage. • Specifically, in our proposed scheme, the data owner can permanently delete the unnecessary outsourced data blocks for saving storage expenditures, while the useful outsourced data blocks still remain on the cloud server. • Meanwhile, the data owner can flexibly insert some new data blocks to dynamically update the outsourced data set. • Then, the data owner can efficiently verify the data integrity to prevent data from pollution. • Our proposed scheme can achieve proof of provable data insertion and deletion without interacting with a third party auditor (TPA), thus avoiding the problems of service interruption and privacy leakage that caused by the single-point-of-failure of TPA. • Meanwhile, we provide the detailed security analysis, which can formally prove that our proposed scheme can satisfy all of the desired security requirements. • Moreover, we implement our proposed scheme and provide the efficiency evaluation, which can intuitively demonstrate the effectiveness, high-efficiency and universality of our proposal in real-world applications. With the widespread popularity of cloud storage, a growing number of data owners are willing to outsource their massive data to remote cloud servers, thus effectively avoiding the heavy burden of storing and managing the massive data by themselves in local physical storage mediums. Despite the tremendous advantages, cloud storage inescapably suffers from some severe security challenges resulting from the separation of outsourced data management and its ownership, such as data integrity, data deletion, and data insertion. In this paper, we aim to deal with the problems of integrity auditing, dynamic insertion and provable deletion over outsourced data. Specifically, we design a novel authentication data structure, namely, number-rank-based Merkle hash tree (NR-MHT), which can achieve data dynamic operations. Meanwhile, NR-MHT can maintain many data blocks in each leaf node, thus effectively solving the problem of the height indefinitely increases with the total number of data blocks. Subsequently, we adopt NR-MHT to propose a new provable data deletion scheme based on efficient data integrity auditing and dynamic data insertion. In our presented scheme, the data owner can not only permanently delete the unnecessary outsourced data blocks to save storage expenditures but also efficiently insert new data blocks to dynamically update the outsourced data set. Meanwhile, we analyze the security to formally demonstrate that our presented scheme can satisfy all of the expected security requirements without interacting with a third party auditor. Finally, we also develop a prototype implementation of our presented scheme and provide an accurate efficiency evaluation. The numerical analysis and experimental results show that compared with the existing schemes, our presented scheme is more attractive in efficiency and practicability.