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

Publication Name

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)


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.

Open Access Status

This publication is not available as open access


13555 LNCS

First Page


Last Page


Funding Number


Funding Sponsor

National Natural Science Foundation of China



Link to publisher version (DOI)