An Efficient Dynamic Proof of Retrievability Scheme

[Abstract] Data security is a significant issue in cloud storage systems. After outsourcing data to cloud servers, clients lose physical control over the data. To guarantee clients that their data is intact on the server side, some mechanism is needed for clients to periodically check the integrity of their data. Proof of retrievability (PoR) is designed to ensure data integrity. However, most prior PoR schemes focus on static data, and existing dynamic PoR is inefficient. In this paper, we propose a new version of dynamic PoR that is based on a B+ tree and a Merkle hash tree. We propose a novel authenticated data structure, called Cloud Merkle B+ tree (CMBT). By combining CMBT with the BLS signature, dynamic operations such as insertion, deletion, and modification are supported. Compared with existing PoR schemes, our scheme improves worst-case overhead from O (n ) to O (log n ).

[Keywords] cloud storage; proof of retrievability; data integrity; B+ tree