1 Introduction
With the availability of cloud storage services, the resource-constraint enterprises and individual clients can outsource their large encrypted database into the cloud storage servers with the manner of storage-as-a-service (STaaS). However, the cloud servers cannot be assumed to be fully trusted, and thus there should exist an efficient solution for the clients to verify the effectiveness of storage services. This is known as the paradigm of verifiable storage, which can be viewed as a special kind of verifiable computation [23], [26], [42]. Recently, plenty of researchers have devoted considerable efforts to the problem of verifiable computation [1], [2], [3], [13], [14], [15], [16], [24], [27], [34], [43], [44], [45] and verifiable storage [5], [8], [10], [17], [19].