Instructor: Zengpeng Li

Guest Instructor: Hong-Sheng Zhou

Course Syllabus

• Models of Secure Computation: Honest vs. Dishonest majority settings, semi-honest vs active(malicious) adversary, static vs. adaptive computation, computational vs. information theoretic security, synchronous vs. asynchronous network...
• Defining Secure Computation: Computational/statistical Indistinguishability, Real-Ideal World or Simulation-based Security notions.
• Secure computation with semi-honest security: Honest-majority Setting: Secret Sharing, BenOr-Goldwasser-Wigderson (BGW) Construction, Optimizations (MPC in preprocessing mode and circuit randomization), Cramer-Damgaard-Neilsen (CDN) Construction. Dishonest majority Setting: Oblivious Transfers (OT), two-party Goldreich-Micali-Wigderson (GMW) construction, Optimizations of GMW (Random input OT and OT extension), Yao construction, BMR construction and multi-party GMW construction.
• Secure computation with Active security: Honest Majority Setting. Verifiable Secret Sharing, BGW Construction with active security, Hyper-invertible Matrices and Beerliova-Hirt (BH) Construction, Information Checking Protocol. Dishonest majority Setting: Commitment Schemes, Zero-knowledge, GMW Compiler for active corruption, Cut-and-Choose OT and Lindell-Pinkas Construction.
• Practical Secure Computation: Secure Set Intersection, Privacy Preserving Biometrics & Genomics, Secure Cloud Computing

Grading:

Schedule of Courses and Presentation Materials

• [March XX: Lecture 1-1]
  Introduction. Computational indistinguishability. Defining secure multi-party computation in the semi-honest setting.
  References:
  • Computational indistinguishability is covered in Katz-Lindell, Chapter 6 or Goldreich, vol. 1, Chapter 3
  • Good surveys of secure computation include Lindell-Pinkas 2008 and Canetti 2006
  
  
• [March XX: Lecture 1-2]
  Defining secure multi-party computation in the semi-honest setting. Real worlds, ideal worlds, and hybrid worlds. Composition.
  References: Definitions of secure computation, and the composition theorem, are covered in Canetti 2000
  scribe notes
  
• [March XX: Lecture 2-1]
  Oblivious transfer (OT) in the semi-honest setting.
  References: Goldreich, vol. 2, Chapter 7, Naor-Pinkas 2001
  scribe notes
  Interesting Links: Tung Chou and Claudio Orlandi. The Simplest Protocol for Oblivious Transfer
  
• [March XX: Lecture 2-2]
  OT in the semi-honest setting, continued. 1-out-of-N OT.
  References: Peikert et al. 2008, Naor-Pinkas 2005
  scribe notes
  
• [April XX: Lecture 2-3]
  OT extension.
  References: Ishai et al. (OT extension),
  scribe notes (Note: the protocol in Section 1.1 is only secure if a single instance of the online phase is run per instance of the pre-processing phase.)
  OT extension lib
  Interesting Links: Yehuda Lindell et al. 2013 Peter Scholl 2020 Arpita Patra Emmanuela Orsini and Peter Scholl
  
• [April XX: Lecture 3-1]
  The GMW protocol. Proof of security for the GMW protocol. Yao's garbled-circuit approach.
  References: Goldreich, vol. 2, Chapter 7 (the GMW protocol), Goldreich, vol. 2, Chapter 7, Lindell-Pinkas 2009
  scribe notes
  
• [April XX: Lecture 3-2]
  Optimizations (and implementations) of garbled circuits.
  References: Kolesnikov-Schneider 2008, PSSW09, Bellare et al. #1, #2, and #3, Asharov et al. 2013
  scribe notes
  
• [April XX: Lecture 3-3]
  Implementations of semi-honest secure two-party computation.
  References: Fairplay, TASTY (see also here), Huang et al. 2011, Choi et al., Schneider-Zohner 2013
  scribe notes
  
• [May XX: Lecture 4-1]
  Beaver Triple Based-Protocols. ABY Secret Sharing. SPDZ Sharing.
  References:
  • Beaver Triple Based-Protocols; ABY Github Repository; SPDZ-2 Github Repository; Multi-Protocol SPDZ Github Repository;
  • ABY from Stanford Uni CS355; ABY from David Wu;
  • MTAT.07.014 Cryptographic Protocols from Pille Pullonen (2020 fall); MTAT.07.014 Cryptographic Protocols from Pille Pullonen (2020 fall);
  • ABY from Peter Scholl (a brief tutorial); ABY at simons from Peter Scholl;
  scribe notes
  
• [May XX: Lecture 9]
  Secure computation using FHE. Oblivious RAM, and secure computation in the RAM model of computation.
  References: Goldreich-Ostrovsky '96 (link only works within UMD), Gordon et al.
  scribe notes
  
• [May XX: Lecture 10]
  Sublinear-time secure computation. "Special-purpose" protocols. Private set intersection.
  References: Freedman et al. 2004, Huang et al. 2012
  scribe notes
  
• [May XX: Lecture 11]
  Semi-honest multi-party computation. Information-theoretic security.
  References: Goldreich, vol. 2, Chapter 7, Asharov-Lindell, Cramer et al., Chapter 3
  scribe notes
  
• [May XX: Lecture 12]
  The BGW protocol in the semi-honest setting, continued. Multi-party computation in constant rounds (the Beaver-Micali-Rogaway protocol).
  References: Rogaway's thesis
  scribe notes
  
• [June XX: Lecture 13]
  Implementations of multi-party computation with semi-honest security. Defining malicious security.
  References:
  • Implementations: FairplayMP, SecureSCM, sugar-beet auction, SEPIA, Sharemind, VIFF, MPC for financial-data analysis, Choi et al.
  • Definitions of malicious security: Canetti 2000, Goldreich, vol. 2, Chapter 7, Lindell-Pinkas 2008
  scribe notes
  
• [June XX: Lecture 14]
  Zero-knowledge proofs/arguments. A zero-knowledge proof of Hamiltonicity.
  References: Goldreich's survey
  scribe notes
  
• [June XX: Lecture 15]
  Sequential vs. parallel composition of ZK proofs. Proofs of knowledge.
  References: Lecture notes from grad cryptography class (note: sometimes buggy)
  scribe notes
  
• [June XX: Lecture 16]
  Witness indistinguishability. A constant-round ZK argument of knowledge. Constant-round two-party coin-tossing with malicious security.
  References: Feige-Shamir, grad crypto scribe notes, Lecture 24, Goldreich, vol. 2, Chapter 7, Lindell 2003
  scribe notes
  
• [June XX: Lecture 17]
  Using zero knowledge for secure multi-party computation (with abort) in the malicious setting (assuming broadcast).
  References: Goldreich, vol. 2, Chapter 7, Lindell 2003
  scribe notes
  
• [June XX: Lecture 18]
  Protocols for broadcast/Byzantine agreement.
  References: Lecture 26, Notes on Byzantine agreement
  
• [June XX: Lecture 19]
  Fully secure computation with honest majority.
  References: Goldreich, vol. 2, Chapter 7
  scribe notes
  
• [June XX: Lecture 20]
  Cut-and-choose for efficient secure two-party computation.
  References: Lindell-Pinkas 2007
  
• [June XX: Lecture 21]
  Efficient two-party computation with 1-bit leakage.
  References: Huang et al.
  scribe notes
  
• [June XX: Lecture 22]
  Knowledge inference for optimizing secure MPC.
  References: Rastogi et al.
  scribe notes
  
• [June XX: Lecture 23]
  Covert security.
  References: Aumann-Lindell, Asharov-Orlandi
  scribe notes
  
• [June XX: Lecture 24]
  Rational secret sharing and multi-party computation.
  References: Gordon-Katz, Fuchsbauer et al., Groce-Katz
  scribe notes
  
• [June XX: Lecture 25]
  The BGW protocol in the malicious setting.
  References: Asharov-Lindell
  scribe notes
  
• [June XX: Lecture 26]
  The BGW protocol in the malicious setting, continued.
  scribe notes
  
• [June XX: Lecture 27]
  Finish up BGW. More efficient cut-and-choose in the two-party setting.
  References: Lindell 2013, Huang et al. 2013
  
• [June XX: Lecture 28]
  Authenticated data structures, generically.
  References: Miller et al.
  
• [June XX: Lecture 29]
  The IPS compiler.
  References: Ishai-Prabhakaran-Sahai, Lindell-Pinkas-Oxman
  
• [June XX: Lecture 30]
  (Efficient) zero knowledge from secure computation.
  References: Ishai et al., Jawurek et al.
  
• [June XX: Lecture 31]
  The Damgard-Orlandi protocol for malicious MPC without honest majority.
  References: Damgard-Orlandi (see also here for an implementation)
  
• [June XX: Lecture 32] Universal composability. Impossibility in the plain model, and UC commitment in the CRS model.
  References: Canetti 2001, Canetti 2006, Canetti-Fischlin, CLOS
  
• [June XX: Lecture 33]
  UC two-party computation in the CRS model.
  References: CLOS
  
• [June XX: Lecture 33]
  Fairness without an honest majority.
  References: Cleve 1986, Moran-Naor-Segev, Gordon-Katz
  
• [June XX: Lecture 34]
  Impossibility results.
  References: Goldreich-Oren, Goldreich-Krawczyk
  
• [Dec 13: Final exam (in class)]
  
  
• Awesome-mpc, maintained by github: https://github.com/rdragos/awesome-mpc.

Useful Lectures and Scribe Notes

• Instructor: Arpita Patra. Secure Computing .
• Instructor: Ran Canetti, Spring 2009. Seminar in Cryptographic Protocols .
• Instructor: Benny Pinkas, Spring semester 2014. Secure Computing .
• FHE-MPC Advanced Grad Course .
• Instructor: Jonathan Katz on Secure Computation: http://www.cs.umd.edu/~jkatz/gradcrypto2/f13/scribes.html.
• Instructor: Mike Rosulek on 2PC Course: https://web.engr.oregonstate.edu/~rosulekm/.

Some Resources for Getting Started with MPC are selected from Yehuda Lindell and Arpita Patra

Books

• David Evans, Vladimir Kolesnikov and Mike Rosulek. A Pragmatic Introduction to Secure Multi-Party Computation, NOW Publishers, 2018. This short book contains a friendly introduction and comprehensive survey of techniques for achieving efficient secure computation. The book does not go into details regarding each technique and does not provide proofs. However, it gives a fantastic overview and pointers to where you can find all of the details. As such, it is an invaluable resource. Refer to Pragmatic MPC.
• Ronald Cramer, Ivan Damgård and Jesper Buus Nielsen. Secure Multiparty Computation and Secret Sharing, Cambridge University Press, 2015. This book includes definitions, constructions for both the computational and information theoretic settings, techniques for efficiency, and more. This is the most comprehensive treatment of the basics of MPC, and I recommend reading it methodically from the beginning.
• Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols: Techniques and Constructions, Springer, 2010. This book focuses specifically on the two-party case and efficiency. It includes definitions, general constructions based on the garbled circuit technique, and chapters on specific tools like oblivious transfer, sigma protocols, and more. The specific techniques for general constructions are outdated (with must faster techniques available today), but the text is very relevant for study and includes basic results like a full proof of the security of Yao's garbled circuits construction.
• Oded Goldreich. Foundations of Cryptography Vol. 2, Cambridge University Press, 2004. Chapter 7 of the book introduces two-party and multiparty computation, contains a thorough and comprehensive definitional treatment, provides a full and detailed proof of the GMW construction, and surveys advanced topics. The book's formal and rigorous treatment makes it a must-read for the MPC researcher.
• Thomas Schneider. Engineering Secure Two-Party Computation Protocols, Springer, 2012. This book focuses specifically tools for optimizing secure computation in practice, including circuit optimizations, frameworks for constructing protocols, and more. The book provides a very good overview of different techniques and tools that MPC researchers should be familiar with.
• Mahdi Zamani and Mahnush Movahedi, Reference on Cryptography, including Notions of Security (e.g., rushing adversary)
• Ittai Abraham. Decentralized Thoughts The power of the adversary.

Survey Papers

• Marcella Hastings, Brett Hemenway, Daniel Noble, and Steve Zdancewic. SoK: General Purpose Compilers for Secure Multi-Party Computation ,
• Yehuda Lindell. Secure Multiparty Computation (MPC), Communications of the ACM, January 2021. This is a general and friendly introduction to secure multiparty computation - what it is, how it works, and what it is used for.
• Yehuda Lindell. How to Simulate It - A Tutorial on the Simulation Proof Technique, 2016. The simulation paradigm is fundamental to secure computation. However, many have difficulties in understanding how to write simulation proofs. This tutorial explains this proof technique in great detail.
• Manoj Prabhakaran and Amit Sahai (Eds.). Secure Multi-Party Computation, IOS Press, 2013. This is a compilation of surveys on the topic of multiparty computation. It focuses on theoretical aspects and is highly useful for those wishing to study the theory of MPC.
• Ran Cannitte. Universally Composable Security: A New Paradigm for Cryptographic Protocols.

Useful Resources on MPC

• Another compilation of MPC resources on Github, maintained by Dragos Rotaru: https://github.com/rdragos/awesome-mpc.
• Cryptography and Information Security Lab, in India: https://www.csa.iisc.ac.in/~cris/index.html.
• BIU Winter School (Events). https://cyber.biu.ac.il/events/.
• MPC Seminars. http://www.cs.tau.ac.il/%7Eiftachh/Courses/Seminars/MPC/Spring17.html and https://www.cs.tau.ac.il/~iftachh/Courses/Seminars/MPC/Intro.pdf.
• Roles of Consortium Partners. https://priviledge-project.eu/consortium.

Video Tutorials

• The 1st BIU Winter School on Secure Computation and Efficiency, 2011. This series of lectures covers the very basics of secure computation and as such is a useful tool.
• The 5th BIU Winter School on Advances in Practical Multiparty Computation, 2015. This series of lectures begins with tutorials and includes many more advanced techniques.
• Ran Canetti. The Universal Composability Framework, 2016. This series of tutorials introduces the universal composability framework in detail.
• Ashish Choudhury. The Universal Composability Framework Course, Secure Computation: Part I