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:

Older research topics:

Graphical summary

Research statement

Blockchain and consensus protocols

The blockchain is a public ledger, maintained by many nodes without central authority using a distributed cryptographic protocol, for recording transactions. The nodes validate the information to be appended to the blockchain, and a consensus protocol ensures that the nodes agree on a unique order in which entries are appended. Distributed protocols tolerating faults and adversarial attacks, coupled with cryptographic mechanisms are needed for this. They related to so-called Byzantine agreement protocols.

Based on our earlier work in distributing trust on the Internet [1], [2], we are exploring consensus protocols and security mechanisms, and apply them in the context of the Hyperledger Project. Hyperledger is an industry-wide effort to develop an open-source blockchain. We have developed protocols for dealing with non-deterministic operations on blockchains [3].

See also this blog post and short video.

  1. Christian Cachin. Distributing trust on the Internet. Proceedings of DSN 2001. Citation.
  2. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming. Springer, 2011. Citation.
  3. Christian Cachin, Simon Schubert, and Marko Vukolic. Non-determinism in Byzantine fault-tolerant replication. e-print, arXiv:1603.07351 [cs.DC], 2016. Citation.

Consistency and intgrity of remote services

Cloud services enable convient online collaboration, but require that clients fully trust the service provider in terms of confidentiality, integrity, and availability. Here we focus on integrity guarantees. A group of clients would like to verify the correctness of the remote computation and the server's responses, specifically in terms of data integrity and consistency of the responses to different clients.

Cryptographic protocols that ensure fork-linearizability help clients to check for violations of integrity and consistency by the untrusted server, even when the clients do not communicate with each other. Such protocols ensure that all clients which observe each other's operations are consistent, in the sense that data has not been tampered with, and that their own and other clients' operations are linearizable. We have developed protocols for efficient remote verification of generic untrusted services [2] and a tool for the Verification of Integrity and Consistency of Cloud Object Storage (VICOS) [1].

  1. Marcus Brandenburger, Christian Cachin, and Nikola Knezevic. Don't trust the cloud, verify: Integrity and consistency for cloud object stores. Proceedings SYSTOR 2015. Citation.
  2. Christian Cachin and Olga Ohrimenko. Verifying the consistency of remote untrusted services with commutative operations. Proceedings OPODIS 2014. Citation.

Cloud security

In cloud computing, the owner loses direct control over its data and programs. After outsourcing data to the cloud, the owner is bound to trust the cloud provider for confidentiality, privacy, integrity, and availability. However, cryptographic mechanisms can reduce such trust by allowing the owner to protect its assets. Moreover distributing data to multiple cloud providers reduces the exposure and eliminates threats originating from a single source.

We have developed protocols for storing data on an Intercloud [1], [2], [3], based on client-side cryptography, replication, and erasure coding. For ensuring that information does get into the wrong hands once it is no longer needed, we have developed tools for secure deletion of data [4].

See also this blog post.

  1. Cristina Basescu, Christian Cachin, Ittay Eyal, Robert Haas, Alessandro Sorniotti, Marko Vukolic, and Ido Zachevsky. Robust data sharing with key-value stores. Proceedings DSN 2012. Citation.
  2. Christian Cachin, Dan Dobre, and Marko Vukolic. Separating data and control: Asynchronous BFT storage with 2t+1 data replicas. Proceedings SSS 2014. Citation.
  3. Elli Androulaki, Christian Cachin, Dan Dobre, and Marko Vukolic. Erasure-coded Byzantine storage with separate metadata. Proceedings OPODIS 2014. Citation.
  4. Christian Cachin, Kristiyan Haralambiev, Hsu-Chun Hsiao, and Alessandro Sorniotti. Policy-based secure deletion. Proceedings ACM CCS 2012. Citation.

Storage integrity (2007-2012)

Users increasingly maintain data in the "cloud" 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, and to ensure consistent operations in environments where multiple users access the data concurrently. We have developed efficient protocols that provide atomic storage and implement arbitrary services consistently when the service is correct and weaker, so-called forking semantics when the server is faulty [2], [6], [7] and discovered fundamental properties of such systems [1], [5]. Applying our approach to the Subversion revision control system, we have demonstrated how to guarantee integrity for a practical online collaboration tool [4]. The Venus system [3] extends our method to securing practical untrusted cloud storage and has been demonstrated and evaluated with Amazon S3.

  1. Matthias Majuntke, Dan Dobre, Christian Cachin, and Neeraj Suri. Fork-consistent constructions from registers. Proceedings of OPODIS 2011. Citation.
  2. Christian Cachin. Integrity and consistency for untrusted services. Proceedings of SOFSEM 2011. Citation.
  3. Alexander Shraer, Christian Cachin, Asaf Cidon, Idit Keidar, Yan Michalevsky, and Dani Shaket. Venus: Verification for untrusted cloud storage. Proceedings of ACM Workshop on Cloud Computing Security, 2010. Citation.
  4. Christian Cachin and Martin Geisler. Integrity protection for revision control. Proceedings of ACNS 2009. Citation.
  5. Christian Cachin, Idit Keidar, and Alexander Shraer. Fork sequential consistency is blocking. Information Processing Letters, March 2009. Citation.
  6. Christian Cachin, Idit Keidar, and Alexander Shraer. Fail-aware untrusted storage. SIAM Journal on Computing, vol. 40, 2011. Citation.
  7. Christian Cachin, abhi shelat, and Alexander Shraer. Efficient fork-linearizable access to untrusted shared memory. Proceedings of PODC 2007, August 2007. Citation.

Management of cryptographic keys (2005-2010)

Cryptographic keys must be maintained securely and reliably. But users struggle with the key-management problem because operating procedures and formats differ across systems. We have built a key-lifecycle management system accessible over a network [1] and led the creation of a new open standard for enterprise key management: the OASIS Key Management Interoperability Protocol (KMIP).

When multiple users access a key server, the interface must be designed with special consideration for cryptographic relations among keys. Cryptographic hardware-security modules (HSMs) face the same problem. Some logical attacks through the key-management operations of HSMs have been reported in the past, which allowed to expose keys merely by exploiting their interfaces in unexpected ways. We show how to secure a key-management system against any attack through its interface. Our design integrates traditional access control with cryptographic semantics, so that the system respects the dependencies among keys introduced through the cryptographic operations [2], [3].

We have also developed a novel key-management scheme with lazy revocation for cryptographic file systems [4], [5].

  1. Mathias Björkqvist, Christian Cachin, Robert Haas, Xiao-Yu Hu, Anil Kurmus, René Pawlitzek, and Marko Vukolic. Design and implementation of a key-lifecycle management system. Proceedings of Financial Cryptography and Data Security, 2010. Citation.
  2. Christian Cachin and Nishanth Chandran. A secure cryptographic token interface. Proceedings of CSF, 2009. Citation.
  3. Christian Cachin, Anil Kurmus, and Marko Vukolic. Strict access control in a key-management server. Proceedings 3rd Workshop on Analysis of Security APIs, July 2009. Citation.
  4. Michael Backes, Christian Cachin, and Alina Oprea. Secure key-updating for lazy revocation. Proceedings of ESORICS, 2006. Citation.
  5. Michael Backes, Christian Cachin, and Alina Oprea. Lazy revocation in cryptographic file systems. Proceedings 3rd IEEE Security in Storage Workshop, 2005. Citation.

Distributing trust on the Internet (2001-2006)

A promising approach to securing critical services lies in distributing the service over a set of geographically and organizationally separated replicas. By using so-called Byzantine-fault tolerant (BFT) coordination algorithms to keep the replicas logically synchronized, the failure or even the malicious corruption of some components can be tolerated.

We have investigated the BFT state-machine replication method [1], 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 were known for environments with random or "benign" faults, but we were among the first to address an adversarial, fully asynchronous network [8]. We have developed the first efficient atomic broadcast protocol [7] for this environment, which preserves safety and liveness through randomization. It builds on a novel practical cryptographic solution for the classical problem of Byzantine agreement [9], using threshold cryptography and randomization. The SINTRA prototype [6] shows that our approach is practical and was used to build a dependable distributed DNS service [5].

Other contributions include the first atomic broadcast protocol for asynchronous networks with linear amortized expected message complexity (in the number of nodes) per delivered payload [4], and several consistency protocols for erasure-coded BFT distributed storage systems [2], [3].

  1. 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.
  2. Christian Cachin and Stefano Tessaro. Optimal resilience for erasure-coded Byzantine distributed storage. Proceedings of DSN 2006. Citation.
  3. Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. Proc. SRDS 2005, October 2005. Citation.
  4. HariGovind V. Ramasamy and Christian Cachin. Parsimonious asynchronous Byzantine-fault-tolerant atomic broadcast. Proceedings of OPODIS 2005, Springer, 2006. Citation.
  5. Christian Cachin and Asad Samar. Secure distributed DNS. Proceedings of DSN 2004. Citation.
  6. Christian Cachin and Jonathan A. Poritz. Secure intrusion-tolerant replication on the Internet. Proceedings of DSN 2002. Citation.
  7. Christian Cachin, Klaus Kursawe, Frank Petzold, and Victor Shoup. Secure and efficient asynchronous broadcast protocols. Proceedings of CRYPTO 2001. Citation.
  8. Christian Cachin. Distributing trust on the Internet. Proceedings of DSN 2001. Citation.
  9. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. Journal of Cryptology, vol. 18, 2005. Citation.

Steganography and information hiding (1998-2004)

Steganography allows to embed a message within another, seemingly harmless message so that its presence cannot be detected. Steganography complements cryptography, whose goal is to protect the content of a message. My interest in steganography is motivated by its relevance for undetectable communication and for watermarking ofdigital content .

We have developed the fundamental ideas for a theory of steganography with information-theoretic security [3], [1]. The topic has subsequently become the focus of many other worksin information theory and it has been extended to a cryptographic model with computational security. Along these lines, we have also defined security for steganography in a public-key cryptographic model and developed a system that protects against active attacks [2].

  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 (1995-2000)

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 assumption is the storage-bounded model [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