Secure Distributed Computing

A course in the doctoral school in computer, communication and information sciences, fall semester 2009.

Summary. The goal of this course is to understand distributed cryptosystems and protocols for distributed systems that use the replication paradigm for tolerating faults or even malicious attacks. The course will consist of two parts: first an introduction to this active area of research, with presentation of the principles; second a seminar-style interactive presentation of classic research papers and recently developed systems by the participants.

Prerequisites. Basic knowledge in cryptography and principles of distributed systems, as offered in courses “Security and Cryptography” and “Distributed Algorithms”.

Lecturer. Dr. Christian Cachin, IBM Research - Zurich, until Dec. 2009 on sabbatical leave at Distributed Programming Laboratory (LPD), EPFL, office INR 327.

Dates. The lecture takes place Tuesdays, 8:15-10:00, in BC02.

Web page. http://lpd.epfl.ch/site/education/secure_distributed_computing

• Secret sharing
• Distributed/threshold cryptosystems
• Asynchronous Byzantine agreement
• Atomic broadcast (Byzantine-fault tolerance, BFT)
• BFT services and storage
• Proactive cryptosystems
• Untrusted storage

Threshold cryptography

• Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, Tal Rabin: Secure Distributed Key Generation for Discrete-Log Based Cryptosystems. J. Cryptology 20(1): 51-83 (2007) DOI: 10.1007/s00145-006-0347-3 http://www.springerlink.com/content/d3m2344060403173/fulltext.pdf

• Victor Shoup, Rosario Gennaro: Securing Threshold Cryptosystems against Chosen Ciphertext Attack. J. Cryptology 15(2): 75-96 (2002) DOI: 10.1007/s00145-001-0020-9 http://www.springerlink.com/content/w3revgfkn4tyjg6c/fulltext.pdf

• Victor Shoup: Practical Threshold Signatures. EUROCRYPT 2000: 207-220 DOI: 10.1007/3-540-45539-6 http://www.springerlink.com/content/kfqvpfejaaue20tl/fulltext.pdf

• Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, Reto Strobl: Asynchronous Verifiable Secret Sharing and Proactive Cryptosystems. ACM Conference on Computer and Communications Security 2002: 88-97 http://doi.acm.org/10.1145/586110.586124

BFT replication protocols

• Miguel Castro, Barbara Liskov: Practical Byzantine Fault Tolerance and Proactive Recovery. ACM Trans. Comput. Syst. 20(4): 398-461 (2002) http://doi.acm.org/10.1145/571637.571640

• Jean-Philippe Martin, Lorenzo Alvisi: Fast Byzantine Consensus. IEEE Trans. Dependable Sec. Comput. 3(3): 202-215 (2006) http://doi.ieeecomputersociety.org/10.1109/TDSC.2006.35 http://www.cs.utexas.edu/~lorenzo/papers/fab.pdf

• Ramakrishna Kotla, Lorenzo Alvisi, Michael Dahlin, Allen Clement, Edmund L. Wong: Zyzzyva: Speculative Byzantine Fault Tolerance. SOSP 2007: 45-58 http://doi.acm.org/10.1145/1294261.1294267

• Chi Ho, Robbert van Renesse, Mark Bickford, Danny Dolev: Nysiad: Practical Protocol Transformation to Tolerate Byzantine Failures. NSDI 2008: 175-188 http://www.usenix.org/events/nsdi08/tech/full_papers/ho/ho.pdf

BFT replication protocols when there are attacks and some applications

• Yair Amir, Brian A. Coan, Jonathan Kirsch, John Lane: Byzantine Replication Under Attack. DSN 2008: 197-206 http://dx.doi.org/10.1109/DSN.2008.4630088

• Atul Singh, Tathagata Das, Petros Maniatis, Peter Druschel, Timothy Roscoe: BFT Protocols Under Fire. NSDI 2008: 189-204 http://www.usenix.org/events/nsdi08/tech/full_papers/singh/singh.pdf

• Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin: Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults, NSDI 09. http://www.usenix.org/events/nsdi09/tech/full_papers/clement/clement.pdf

• Ben Vandiver, Hari Balakrishnan, Barbara Liskov, Samuel Madden: Tolerating Byzantine Faults in Transaction Processing Systems Using Commit Barrier Scheduling. SOSP 2007: 59-72 http://doi.acm.org/10.1145/1294261.1294268

• Christian Cachin, Asad Samar: Secure Distributed DNS. DSN 2004: 423-432 DOI 10.1109/DSN.2004.1311912 http://www.zurich.ibm.com/~cca/papers/dnsrepl.pdf

Cryptographic algorithms for storage integrity

• Manuel Blum, William S. Evans, Peter Gemmell, Sampath Kannan, Moni Naor: Checking the Correctness of Memories. Algorithmica 12(2/3): 225-244 (1994) DOI: 10.1007/BF01185212 http://www.springerlink.com/content/mq831jr823224358/fulltext.pdf

• Cynthia Dwork, Moni Naor, Guy N. Rothblum, Vinod Vaikuntanathan: How Efficient Can Memory Checking Be?. TCC 2009: 503-520 DOI: 10.1007/978-3-642-00457-5_30 http://springerlink.metapress.com/content/umk0608404rlh0x4/fulltext.pdf

• C. Papamanthou, R. Tamassia and N. Triandopoulos, Authenticated Hash Tables. ACM CCS 2008: 437-448 http://doi.acm.org/10.1145/1455770.1455826

• Alina Oprea and Kevin D. Bowers: Authentic Time-Stamps for Archival Storage , ESORICS 2009 http://www.springerlink.com/content/rr2254820k84u487/fulltext.pdf and http://eprint.iacr.org/2009/306

Systems providing storage integrity

• Alina Oprea, Michael K. Reiter: Space-Efficient Block Storage Integrity. NDSS 2005 http://www.isoc.org/isoc/conferences/ndss/05/proceedings/papers/storageint.pdf

• Byung-Gon Chun, Petros Maniatis, Scott Shenker, John Kubiatowicz: Attested Append-Only Memory: Making Adversaries Stick to Their Word. SOSP 2007: 189-204 http://doi.acm.org/10.1145/1294261.1294280

• Carsten Weinhold, Hermann Härtig: VPFS: Building a Virtual Private File System with a Small Trusted Computing Base. EuroSys 2008: 81-93 http://doi.acm.org/10.1145/1352592.1352602

There will be an oral final exam.

The grade will respect the quality of the paper presentations and the grade in the exam.

Last updated: 10 Nov. 2009.