Efficient dynamic provable possession of remote data via balanced update trees

Abstract

The emergence and availability of remote storage providers prompted work in the security community that allows a client to verify integrity and availability of the data she outsourced to an untrusted remove storage server at a relatively low cost. Most recent solutions to this problem allow the client to read and update (insert, modify, or delete) stored data blocks while trying to lower the overhead associated with verifying data integrity. In this work we develop a novel and efficient scheme, computation and communication overhead of which is orders of magnitude lower than those of other state-of-the-art schemes. Our solution has a number of new features such as a natural support for operations on ranges of blocks, and revision control. The performance guarantees that we achieve stem from a novel data structure, termed balanced update tree, and removing the need to verify update operations.