A Semantic Hash Tree Based Verifiable Data Access Protocol on the Cloud

With the popularity of outsourcing data to the cloud, security of cloud storage has drawn considerable attention. While many research efforts have been devoted to verifying the availability and integrity of the outsourced data, it remains a critical challenge how to efficiently verify the correctness of the cloud´s response on data access request. In particular, when a user requests a data item from a mobile or Web interface, what if the cloud claims that the data item does not exist while the item does exist? We refer to this as verifiable data access. In this paper, we present a formal model for verifiable data access, and then propose a privacy-preserving and provably secure protocol to address the problem. In order to achieve the verifiability, we develop a novel mechanism called semantic hash tree. Through a sophisticated design of such a tree, our protocol supports verifiable data access in constant time with logarithm communication cost. Experimental evaluation further validates the practicality and efficiency of our protocol.