Lectures and scribe notes

• [Sep 4: Lecture 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
  
  
• [Sep 6]
  Class cancelled.
  
  
• [Sep 9: Lecture 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
  
  
• [Sep 11: Lecture 3]
  Oblivious transfer (OT) in the semi-honest setting.
  References: Goldreich, vol. 2, Chapter 7, Naor-Pinkas 2001
  scribe notes
  
  
• [Sep 13: Lecture 4]
  OT in the semi-honest setting, continued. 1-out-of-N OT.
  References: Peikert et al. 2008, Naor-Pinkas 2005
  scribe notes
  
  
• [Sep 16: Lecture 5]
  OT extension. The GMW protocol.
  References: Ishai et al. (OT extension), Goldreich, vol. 2, Chapter 7 (the GMW protocol)
  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.)
  
  
• [Sep 18: Lecture 6]
  Proof of security for the GMW protocol. Yao's garbled-circuit approach.
  References: Goldreich, vol. 2, Chapter 7, Lindell-Pinkas 2009
  scribe notes
  
  
• [Sep 20: Lecture 7]
  Class cancelled.
  
  
• [Sep 23: Lecture 8]
  Optimizations (and implementations) of garbled circuits.
  References: Kolesnikov-Schneider 2008, PSSW09, Bellare et al. #1, #2, and #3, Asharov et al. 2013
  scribe notes
  
  
• [Sep 25: Lecture 9]
  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
  
  
• [Sep 27: Lecture 10]
  Class cancelled.
  
  
• [Sep 30: Lecture 11]
  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
  
  
• [Oct 2: Lecture 12]
  Sublinear-time secure computation. "Special-purpose" protocols. Private set intersection.
  References: Freedman et al. 2004, Huang et al. 2012
  scribe notes
  
  
• [Oct 4: Lecture 13]
  Semi-honest multi-party computation. Information-theoretic security.
  References: Goldreich, vol. 2, Chapter 7, Asharov-Lindell, Cramer et al., Chapter 3
  scribe notes
  
  
• [Oct 7: Lecture 14]
  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
  
  
• [Oct 9: Lecture 15]
  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
  
  
• [Oct 11: Lecture 16]
  Zero-knowledge proofs/arguments. A zero-knowledge proof of Hamiltonicity.
  References: Goldreich's survey
  scribe notes
  
  
• [Oct 14: Lecture 17]
  Sequential vs. parallel composition of ZK proofs. Proofs of knowledge.
  References: Lecture notes from grad cryptography class (note: sometimes buggy)
  scribe notes
  
  
• [Oct 16: Lecture 18]
  Class cancelled.
  
  
• [Oct 18: Lecture 19]
  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
  
  
• [Oct 21: Lecture 20]
  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
  
  
• [Oct 23: Lecture 21]
  Protocols for broadcast/Byzantine agreement.
  References: Lecture 26, Notes on Byzantine agreement
  
  
• [Oct 25: Lecture 22]
  Fully secure computation with honest majority.
  References: Goldreich, vol. 2, Chapter 7
  scribe notes
  
  
• [Oct 28: Lecture 23]
  Class cancelled.
  
  
• [Oct 30: Midterm exam]
  
  
• [Nov 1: Lecture 24]
  Cut-and-choose for efficient secure two-party computation.
  References: Lindell-Pinkas 2007
  
  
• [Nov 4: Lecture 25]
  Efficient two-party computation with 1-bit leakage.
  References: Huang et al.
  scribe notes
  
  
• [Nov 6: Lecture 26]
  Knowledge inference for optimizing secure MPC.
  References: Rastogi et al.
  scribe notes
  
  
• [Nov 8: Lecture 27]
  Covert security.
  References: Aumann-Lindell, Asharov-Orlandi
  scribe notes
  
  
• [Nov 11: Lecture 28]
  Rational secret sharing and multi-party computation.
  References: Gordon-Katz, Fuchsbauer et al., Groce-Katz
  scribe notes
  
  
• [Nov 13: Lecture 29]
  The BGW protocol in the malicious setting.
  References: Asharov-Lindell
  scribe notes
  
  
• [Nov 15: Lecture 30]
  The BGW protocol in the malicious setting, continued.
  scribe notes
  
  
• [Nov 18: Lecture 31]
  Finish up BGW. More efficient cut-and-choose in the two-party setting.
  References: Lindell 2013, Huang et al. 2013
  
  
• [Nov 20: Lecture 32]
  Authenticated data structures, generically.
  References: Miller et al.
  
  
• [Nov 22: Lecture 33]
  The IPS compiler.
  References: Ishai-Prabhakaran-Sahai, Lindell-Pinkas-Oxman
  
  
• [Nov 25: Lecture 34]
  (Efficient) zero knowledge from secure computation.
  References: Ishai et al., Jawurek et al.
  
  
• [Nov 27: Lecture 35]
  Student presentations.
  
  
• [Dec 2: Lecture 36]
  The Damgard-Orlandi protocol for malicious MPC without honest majority.
  References: Damgard-Orlandi (see also here for an implementation)
  
  
• [Dec 4: Lecture 37] Universal composability. Impossibility in the plain model, and UC commitment in the CRS model.
  References: Canetti 2001, Canetti 2006, Canetti-Fischlin, CLOS
  
  
• [Dec 6: Lecture 38]
  UC two-party computation in the CRS model.
  References: CLOS
  
  
• [Dec 9: Lecture 39]
  Fairness without an honest majority.
  References: Cleve 1986, Moran-Naor-Segev, Gordon-Katz
  
  
• [Dec 11: Lecture 40]
  Impossibility results.
  References: Goldreich-Oren, Goldreich-Krawczyk
  
  
• [Dec 13: Final exam (in class)]