One student will scribe the lectures for each week -- i.e., three lectures. Please email me the .tex and .pdf within 2 weeks of the last lecture.

**[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

**[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)]**