Public Cloud Data Auditing Revisited: Removing the Tradeoff Between Proof Size and Storage Cost

Public cloud data auditing allows any third party to check the integrity of data stored on untrusted cloud servers without retrieving the data. The challenge is how to audit the proof of storage with efficient communications. In ACM CCS 2007, Ateniese et al. described the first practical public cloud data auditing scheme based on RSA, in which the proof of storage consists of one RSA element and one hash value and the storage cost for generating the proof can be as short as 1% of the stored file. Soon after, in Asiacrypt 2008, Shacham and Waters gave another public cloud data auditing scheme based on bilinear pairing, in which the generated proof of storage can be as short as 320 bits for 80-bit security (71% less compared to Ateniese et al.'s scheme). However, Shacham and Waters' scheme must trade off the storage cost, where the storage overhead for generating the proof of storage must be 100% of the stored file. Surprisingly, until today, the tradeoff between the proof size (namely proof of storage) and the storage cost (namely storage overhead) in cloud data auditing remains an open problem. In this paper, we introduce a completely new public cloud data auditing mechanism. The proof of storage is not computed from block tags directly, but from evolution tags that are still unforgeable and evolved from bunch tags. We propose a concrete public cloud data auditing scheme based on this mechanism, in which the proof size is 240 bits for 80-bit security (25% less compared to Shacham and Waters' scheme) and the storage cost can be as efficient as Ateniese et al.'s scheme. The core of our technique is the feasibility of tag aggregations within this new mechanism. Our scheme is provably secure in the random oracle model.

Automated summary

Public cloud data auditing allows third parties to verify data integrity on untrusted servers without retrieving the data. Different schemes based on RSA and bilinear pairing have been proposed with trade-offs between proof size and storage cost. However, the balance between proof size and storage cost in cloud data auditing remains an open problem.