Paper 2014/886

Accountable Storage

Giuseppe Ateniese, Michael T. Goodrich, Vassilios Lekakis, Charalampos Papamanthou, Evripidis Paraskevas, and Roberto Tamassia


We introduce Accountable Storage, a framework allowing a client with small local space to outsource n file blocks to an untrusted server and be able (at any point in time after outsourcing) to provably compute how many bits have been discarded by the server. Such protocols offer ``provable storage insurance" to a client: In case of a data loss, the client can be compensated with a dollar amount proportional to the damage that has occurred, forcing the server to be more ``accountable" for his behavior. The insurance can be captured in the SLA between the client and the server. 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.

Note: We revised the affiliation of some co-authors of the paper

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Cloud StorageData RecoveryInvertible Bloom FiltersBitcoin
Contact author(s)
cpap @ umd edu
2014-12-04: last of 2 revisions
2014-10-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giuseppe Ateniese and Michael T.  Goodrich and Vassilios Lekakis and Charalampos Papamanthou and Evripidis Paraskevas and Roberto Tamassia},
      title = {Accountable Storage},
      howpublished = {Cryptology ePrint Archive, Paper 2014/886},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.