International Association
for Cryptologic Research

The emergence and wide availability of remote storage service providers prompted work in

the security community that allows a client to verify integrity and availability of the data that

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 (i.e., insert, modify, or delete)

stored data blocks while trying to lower the overhead associated with verifying the integrity

of the stored data. In this work we develop a novel scheme, performance of which favorably

compares with the existing solutions. Our solution enjoys a number of new features such as a

natural support for operations on ranges of blocks, revision control, and support for multiple

user access to shared content. The performance guarantees that we achieve stem from a novel

data structure termed a balanced update tree and removing the need to verify update operations.