Although applying existing techniques (e.g., proof-of-storage protocols) could address the problem, the related costs of such approaches are prohibitive. Instead, our protocols can provably compute the damage that has occurred through an efficient recovery process of the lost or corrupted file blocks, which requires only sublinear $O(\delta\log n)$ communication, computation and local space, where $\delta$ is the maximum number of corrupted file blocks that can be tolerated. Our technique is based on an extension of invertible Bloom filters, a data structure used to quickly compute the distance between two sets.
Finally, we show how our protocol can be integrated with Bitcoin, to support automatic compensations proportional to the number of corrupted bits at the server. We also build and evaluate our protocols showing that they perform well in practice.Category / Keywords: Cryptographic Protocols/Cloud Storage; Data Recovery; Invertible Bloom Filters; Bitcoin Date: received 27 Oct 2014, last revised 4 Dec 2014 Contact author: cpap at umd edu Available format(s): PDF | BibTeX Citation Note: We revised the affiliation of some co-authors of the paper Version: 20141204:210958 (All versions of this report) Short URL: ia.cr/2014/886 Discussion forum: Show discussion | Start new discussion