Paper 2019/1143

Auditable Compressed Storage

Iraklis Leontiadis and Reza Curtmola


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ISC19
Proofs of RetrievabilityProofs of Data PossessionCompressed StorageAuditing
Contact author(s)
iraklis @ inpher io
2019-10-03: revised
2019-10-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Iraklis Leontiadis and Reza Curtmola},
      title = {Auditable Compressed Storage},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1143},
      year = {2019},
      doi = {10.1007/978-3-030-30215-3_4},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.