Christian Cachin - Research Interests

My research focuses on information security and distributed systems, with emphasis on secure protocols for distributed systems. Current research topics are the security of storage systems, particularly storage integrity, and distributing trust on the Internet. I am also interested in steganography and have done research on cryptographic protocols at large.

Security of storage systems

Protecting data at rest in storage systems poses new challenges compared to protecting data in flight, which has been the focus of communication security for some time and is well understood today. One notable difference between these two problems is that communication channels typically use a streaming interface with FIFO characteristic, whereas storage systems must provide random access to small portions of the stored data. New techniques are needed for providing security in this context, in particular for protecting the integrity of stored data efficiently. I have recently worked on the following questions in storage security: the performance of cryptographic file systems [2], key management and user revocation schemes for cryptographic file systems [3], [4], and consistency protocols for erasure-coded distributed storage systems [5], [6]. I have also developed a tutorial on cryptographic methods for securing storage systems [1].
  1. Christian Cachin. Cryptographic methods for protecting storage systems. Tutorial at USENIX FAST '08, IEEE MSST 2007, and ACM CCS 2006.
  2. Roman Pletka and Christian Cachin. Cryptographic security for a high-performance distributed file system. Proc. IEEE MSST 2007. Citation.
  3. Michael Backes, Christian Cachin, and Alina Oprea. Secure key-updating for lazy revocation. Proc. ESORICS 2006, 2006. Citation.
  4. Michael Backes, Christian Cachin, and Alina Oprea. Lazy revocation in cryptographic file systems. Proc. 3rd IEEE Security in Storage Workshop, 2005. Citation.
  5. Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. Proc. SRDS 2005, October 2005. Citation.
  6. Christian Cachin and Stefano Tessaro. Optimal resilience for erasure-coded Byzantine distributed storage. Proceedings of DSN 2006. Citation.

Storage integrity

Users increasingly maintain data at remote storage service providers. Such services allow users to collaborate with each other and to access the shared data from everywhere. It is important to guarantee the integrity of the data when the service is not trusted. We have developed efficient protocols that provide atomic storage when the service is correct and weaker, so-called forking semantics when the server is faulty [4], [3], [2]. Applying our approach to the Subversion revision control system, we have demonstrated how to guarantee integrity for a practical online collaboration tool [1].

  1. Christian Cachin and Martin Geisler. Integrity protection for revision control. Proceedings of ACNS 2009. Citation.
  2. Christian Cachin, Idit Keidar, and Alexander Shraer. Fork sequential consistency is blocking. Information Processing Letters, March 2009. Citation.
  3. Christian Cachin, Idit Keidar, and Alexander Shraer. Fail-aware untrusted storage. Proceedings of DSN 2009. Citation.
  4. Christian Cachin, abhi shelat, and Alexander Shraer. Efficient fork-linearizable access to untrusted shared memory. Proc. PODC 2007, August 2007. Citation.

Distributing trust on the Internet

Today's information infrastructure relies on a few critical network services to function properly. I am convinced that such a critical service can only function reliably in an environment where malicious attacks abound, if the service is distributed among several components and does not have any single point of failure. By implementing a service using a set of geographically distributed and organizationally separated service replicas, and through using coordination algorithms to keep the replicas logically synchronized, the failure or even the malicious corruption of some components can be tolerated.

Our approach is based on the state-machine replication method [7], where a request to a service is processed by all components and the client infers the result from a majority of the received answers. Many protocols for this task are known for environments with random or ``benign'' faults, but we are among the first to address an adversarial, fully asynchronous network, such as the Internet [4]. We have developed the first efficient atomic broadcast protocol [3] for this environment, exploiting novel cryptographic protocols. The atomic broadcast protocol builds on a practical cryptographic solution for the classical problem of Byzantine agreement [5], which is implemented through modern threshold cryptography and revisits the old idea of randomization. The implementation of the SINTRA prototype [2] shows that these protocols are practical.

We have shown how to implement a dependable DNS service using SINTRA and threshold cryptography [1], providing fault tolerance and security for a DNS zone even if up to a fraction of authoritative servers have been corrupted and actively misbehave. Another contribution is the first atomic broadcast protocol for asynchronous networks with linear amortized expected message complexity (in the number of nodes) per delivered payload [6]. It uses inexpensive mechanisms during periods when no faults occur, and when network instability or faults are detected, it switches to a more expensive recovery mode.

  1. Christian Cachin and Asad Samar. Secure distributed DNS. Proceedings of DSN 2004. Citation.
  2. Christian Cachin and Jonathan A. Poritz. Secure intrusion-tolerant replication on the Internet. Proceedings of DSN 2002. Citation.
  3. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. Proceedings of CRYPTO 2001. Citation.
  4. Christian Cachin. Distributing trust on the Internet. Proceedings of DSN 2001. Citation.
  5. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. Journal of Cryptology, vol. 18, 2005. Citation.
  6. HariGovind V. Ramasamy and Christian Cachin. Parsimonious asynchronous Byzantine-fault-tolerant atomic broadcast. Proceedings of OPODIS 2005, Springer, 2006. Citation.
  7. Christian Cachin. State machine replication with Byzantine faults, A survey based on a talk given at the seminar A 30-year perspective on replication, Monte Verita, Switzerland, Nov. 2007. Citation.

Some of this work is part of MAFTIA. For more information, check out this project page.

Steganography and information hiding

Steganography allows to embed a message within another, seemingly harmless message so that its presence cannot be detected. It seems that steganography complements cryptography, whose goal is to protect the content of a message. My interest in steganography is motivated by its relevance for digital content protection using related methods from watermarking and fingerprinting.

We have developed the fundamental ideas for a theory of steganography with information-theoretic security [1], [2]. The topic has subsequently become the focus of several other works, which extend the theory to a computational security model. Along these lines, we have also defined security for steganography in a public-key model that protects against active attacks [2]. I am convinced that interesting applications of information hiding are waiting to be discovered, in particular those resulting from practical exploitation of the recently developed theoretical approach.

  1. Christian Cachin. Digital steganography. Survey prepared for the Encyclopedia of Cryptography and Security, 2005. Citation.
  2. Michael Backes and Christian Cachin. Public-key steganography with active attacks. Proc. 2nd Theory of Cryptography Conference (TCC 2005). Citation.
  3. Christian Cachin. An information-theoretic model for steganography. Information and Computation, vol. 192, July 2004. Citation.

Cryptographic protocols

The wish to jointly execute a computational task between two or more mutually distrusting parties lies the core of most security problems. Mobile code and mobile agents are prominent examples. We have formulated the problem of mobile code security more precisely and shown that a surprisingly large class of computations can be performed in an encrypted fashion [1], but that for most practical scenarios, additional trusted components are needed [2]; the same holds if fairness is desired [3].

Cryptography has identified the fundamental role of the so-called oblivious transfer task; given a protocol for it, one can build arbitrarily complex secure protocols. My research has concentrated on several aspects of oblivious transfer [4], [5], on the problem of private information retrieval [6], and on a related application to secure auctions [7]. In my thesis work I addressed cryptographic protocols with information-theoretic security [8], [9], [10]; a particularly attractive model is the one of [5], [8], in which only the storage space of an adversary is bounded, but not its computational power.

  1. Christian Cachin, Jan Camenisch, Joe Kilian, and Joy Müller. One-round secure computation and secure autonomous mobile agents. Proceedings of ICALP 2000. Citation.
  2. Joy Algesheimer, Christian Cachin, Jan Camenisch, and Günter Karjoth. Cryptographic security for mobile code. Proceedings of IEEE Security & Privacy 2001. Citation.
  3. Christian Cachin and Jan Camenisch. Optimistic fair secure computation. Proceedings of CRYPTO 2000. Citation.
  4. Christian Cachin. On the foundations of oblivious transfer. Proceedings of EUROCRYPT '98. Citation.
  5. Christian Cachin, Claude Crépeau, and Julien Marcil. Oblivious transfer with a memory-bounded receiver. Proceedings of FOCS '98. Citation.
  6. Christian Cachin, Silvio Micali, and Markus Stadler. Computationally private information retrieval with polylogarithmic communication. Proceedings of EUROCRYPT '99. Citation.
  7. Christian Cachin. Efficient private bidding and auctions with an oblivious third party. Proceedings of ACM CCS 1999. Citation.
  8. Christian Cachin and Ueli Maurer. Unconditional security against memory-bounded adversaries. Proceedings of CRYPTO '97. Citation.
  9. Christian Cachin. Smooth entropy and Rényi entropy. Proceedings of EUROCRYPT '97. Citation.
  10. Christian Cachin and Ueli Maurer. Linking information reconciliation and privacy amplification. Journal of Cryptology, vol. 10, 1997. Citation.

The list of publications includes other formats and citation details.

Christian Cachin