Securing Data on Untrusted Storage

Christian Cachin
IBM Zurich (Switzerland)


Future distributed data storage systems will rely on cryptographic protection methods as a key technology. This talk addresses two related methods to guarantee the integrity of data stored on an untrusted server. When multiple clients access the shared storage space, a misbehaving server may always delay or leave out an update operation of some client in the view presented to the other clients. Mazières and Shasha (PODC 2002) proposed a protocol to ensure that two clients, whose views differ in as little as one operation from each other, may never again see each other's updates. Since the two clients remain isolated from each other, any misbehavior of the server can easily be detected through out-of-band communication. We give novel results about fork consistency and show a simple protocol that emulates a fork-consistent shared storage space with linear complexity in the number of clients. It is well-known that integrity protection for large sets of data is obtained by authenticating the root hash value of a Merkle tree computed from the data blocks. However, advice on the design choices for implementing Merkle trees in file systems is sparse. We describe an experimental comparison of different implementation strategies for Merkle trees in a file system prototype. This talk is based on joint work with Björn Lalin, Abhi Shelat, and Alex Shraer.