Official arbitration with secure cloud storage application

Abstract

In a secure cloud storage setting, a client outsources storage of her data to a server, who may, willingly or not, corrupt the data, or delete infrequently accessed parts to save space. Existing proof of storage schemes only solve part of this problem: The client may obtain a cryptographic proof of integrity. But what happens if this proof fails to verify? We argue that in such a case, both the client and the server should be able to contact an official court, providing cryptographic proofs, to resolve this dispute. We show that, this property is stronger than what is known as public verifiability since we must handle a malicious client as well. We present multiple schemes that work for various static and dynamic storage solutions. We showimplementation results where the overhead for adding the ability to resolve such disputes at a court is only 2 ms and 80 bytes for each update on the stored data, using standard desktop hardware. Finally, we note that disputes may arise in many other situations, such as when two parties exchange items (e.g. e-commerce) or agree on something (e.g. contract-signing). We extend our official arbitration protocols for a general case, including dynamic authenticated data structures.