Security and Privacy Applied Research Lab

Protecting Data Integrity on Untrusted Storage

Christian Cachin
IBM Zurich Research


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 faulty server may always delay or leave out an update operation of some client in the view presented to the other clients. MaziEres and Shasha (PODC 2002) proposed a protocol to ensure that two clients, whose views have diverged from each other in as little as one operation, may never again see each other's updates after the split. This property of a storage access protocol has been called fork-linearizability. We show how to implement a fork-linearizable storage protocol with linear communication complexity (instead of quadratic) in the number of clients. We also illustrate why, in every such protocol, a reader must wait for a concurrent writer.

It is well-known that the integrity of a large number of stored data blocks can be protected by authenticating the root hash value of a Merkle tree computed from the blocks. However, advice on the design choices for implementing Merkle trees in file systems is sparse. We describe implementation strategies for Merkle trees in a file system prototype and experiments comparing the alternatives. This talk is based on joint work with Bjorn Lalin, Abhi Shelat, and Alex Shraer.


Christian Cachin. Ph.D. in Computer Science from ETH Zurich, 1997; from 1997-1998 postdoctoral researcher at MIT Laboratory for Computer Science; since 1998 Research Staff Member at IBM Zurich Research Lab. His research interests are cryptography, network security, distributed systems, storage security, and information hiding. He is a Director of the IACR and was program chair of Eurocrypt 2004.