Auditable Compressed Storage

Outsourcing data to the cloud for personal use is becoming an everyday trend rather than an extreme scenario. The frequent outsourcing of data increases the possible attack window because users do not fully control their personal files. Typically, once there are established secure channels between two endpoints, communication is considered secure. However, in the cloud model the receiver–the cloud–cannot be fully trusted, either because it has been under adversarial control, or because it acts maliciously to increase its revenue by deleting infrequent accessed file blocks. One approach used by current literature to address the aforementioned security concerns is via Remote Data Integrity Checking (RDIC) protocols, whereby a data owner can challenge an untrusted cloud service provider (CSP) to prove faithful storage of its data. Current RDIC protocols assume that the original data format remains unchanged. However, users may wish to compress their data in order to enjoy less charges. In that case, current RDIC protocols become impractical because, each time compression happens on a file, the user has to run a new RDIC protocol. In this work we initiate the study for Auditable Compressed Storage (ACS). After defining the new model we instantiate two protocols for different widely used compression techniques: run length encoding and Huffman encoding. In contrast with conventional RDIC, our protocols allow a user to delegate the compression to the cloud in a provably secure way: The client can verify correctness of compression without having to download the entire uncompressed file and check it against the compressed one.