Protecting Data Integrity on Untrusted Storage
Christian Cachin
IBM Zurich Research
Abstract
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.
Biography
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.