A dynamic Proof of Retrievability (PoR) scheme with O(logn) complexity

Cloud storage has been gaining popularity because its elasticity and pay-as-you-go manner. However, this new type of storage model also brings security challenges. This paper studies the problem of ensuring data integrity in cloud storage. In the Proof of Retrievability (PoR) model, after outsourcing the preprocessed data to the server, the client will delete its local copies and only store a small amount of meta data. Later the client will ask the server to provide a proof that its data can be retrieved correctly. However, most of the prior PoR works apply only to static data. The existing dynamic version of PoR scheme has an efficiency problem. In this paper, we extend the static PoR scheme to dynamic scenario. That is, the client can perform update operations, e.g., insertion, deletion and modification. After each update, the client can still detect the data losses even if the server tries to hide them. We develop a new version of authenticated data structure based on a B+ tree and a merkle hash tree. We call it Cloud Merkle B+ tree (CMBT). By combining the CMBT with the BLS signature, we propose a dynamic version of PoR scheme. Compared with the existing dynamic PoR scheme, our worst case communication complexity is O(logn) instead of O(n).