Lectures and scribe notes

• [Jan 26: Lecture 1]
  Computational indistinguishability. Secure computation. Defining secure multi-party computation in the semi-honest setting, and secure two-party computation in the malicious setting.
  References:
  • Computational indistinguishability: Katz-Lindell (Chapter 8), Goldreich (Chapter 3)
  • Surveys of secure computation: Canetti 2006, Lindell-Pinkas 2008, Archer et al. 2018, Lindell 2020
  • Definitions of secure computation: Goldreich (Chapter 7), Canetti 2000 (journal version).
  Class presentation | lecture notes (latex source)
  
  
• [Jan 28: Lecture 2]
  Hybrid worlds and sequential/modular composition. The oblivious-transfer (OT) functionality and semi-honest OT.
  References: Canetti 2000 [journal version] (composition), Goldreich (Chapter 7) (OT)
  Class presentation | lecture notes (latex source)
  
  
• [Feb 2: Lecture 3]
  The GMW protocol for semi-honest secure two-party computation.
  References: Goldreich (Chapter 7)
  Class presentation | lecture notes
  
  
• [Feb 4: Lecture 4]
  The GMW protocol for semi-honest secure multi-party computation. Yao's garbled-circuit approach for constant-round, semi-honest, secure two-party computation.
  References: Lindell-Pinkas 2009
  Class presentation | lecture notes
  
  
• [Feb 9: Lecture 5]
  Improved circuit-garbling techniques.
  References:
  • Garbling syntax/security
  • Improved garbling techniques: free-XOR, Pinkas et al., Bellare et al., half gates, Guo et al., free-if
  • You may also find these notes on garbled circuits useful
  Class presentation
  
  
• [Feb 11: Lecture 6]
  The BMR protocol for constant-round, semi-honest, secure multi-party computation. The BGW protocol for semi-honest, perfectly secure multi-party computation.
  References:
  • BMR protocol: Rogaway's thesis, Pragmatic MPC (Section 3.5)
  • BGW protocol: Asharov-Lindell 2014
  Class presentation
  
  
• [Feb 16: Lecture 7]
  The BGW protocol for semi-honest, perfectly secure multi-party computation. Beaver triples.
  References:
  • BGW protocol: Simplified VSS and fast-track MPC, Asharov-Lindell 2014
  • Beaver triples: Beaver '92
  Class presentation
  
  
• [Feb 18: Lecture 8]
  Class canceled due to snow.
  
  
• [Feb 23: Lecture 9]
  OT preprocessing and extension. Defining malicious security in the two-party setting. Zero-knowledge proofs and witness indistinguishability; proofs of knowledge.
  References:
  • OT extension: Ishai et al. 2003
  • Defining malicious security: Goldreich (Chapter 7)
  • Zero knowledge: Katz lecture notes, Lindell 2012, Goldreich (Chapter 4), Goldreich 2010, Lindell 2016
  Class presentation
  
  
• [Feb 25: Lecture 10]
  Zero-knowledge proofs and witness indistinguishability; proofs of knowledge.
  References: Katz lecture notes, Lindell 2012, Goldreich (Chapter 4), Goldreich 2010, Lindell 2016
  Class presentation
  
  
• [Mar 2: Lecture 11]
  The Goldreich-Kahan and Feige-Shamir protocols.
  References: Feige-Shamir (ZK argument of knowledge), Goldreich-Kahan (ZK proof), Katz lecture notes
  Class presentation
  
  
• [Mar 4: Lecture 12]
  The no-honest-majority GMW compiler. Defining secure multi-party computation in the malicious setting.
  References:
  • The GMW compiler: Goldreich (Chapter 7)
  • Coin tossing: Lindell 2003
  • Notions of agreement, fairness, and guaranteed output delivery: Goldwasser-Lindell 2002, Cohen-Lindell 2014
  Class presentation
  
  
• [Mar 9: Lecture 13] -- Midterm out
  The honest-majority GMW compiler. Byzantine agreement/broadcast.
  References:
  • The GMW compiler: Goldreich (Chapter 7)
  • Broadcast: Katz notes on broadcast/Byzantine agreement
  Class presentation
  
  
• [Mar 11: Lecture 14]
  Byzantine agreement/broadcast.
  References: Katz notes on broadcast/Byzantine agreement
  Class presentation
  
  
• [Mar 23: Lecture 15]
  Efficient actively secure two-party computation.
  References:
  • Circuit-level cut-and-choose: Lindell-Pinkas 2007, Lindell-Pinkas 2011, Lindell 2013
  • Gate-level cut-and-choose: LEGO
  • Authenticated garbling: Wang et al. 2017
  Additional references: survey, Afshar et al. 2014, MiniLEGO, TinyLEGO (implementation), Hazay et al. 2017, Katz et al. 2018, Frederiksen thesis
  Class presentation
  
  
• [Mar 25: Lecture 16]
  Efficient actively secure multi-party computation.
  References:
  • Protocols: SPDZ, SPDZ II, SPDZ III, honest-majority MPC
  • Practical considerations: MPC as a service, generalizing the SPDZ compiler, SoK: MPC compilers
  Additional references: MASCOT, multi-party authenticated garbling, Hazay et al., (1,4)-resilient MPC, TinyKeys I, TinyKeys II, large-scale honest-majority MPC, 1/3-resilient MPC, Yang et al., SCALE-MAMBA website
  Class presentation
  
  
• [Mar 30: Lecture 17]
  Differential privacy I: the centralized model.
  References: Dwork-Roth, Vadhan
  Class presentation
  
  
• [Apr 1: Lecture 18]
  Differential privacy II: local differential privacy.
  References: Dwork-Roth, Vadhan, RAPPOR (Google)
  Additional references: Learning with privacy at scale (Apple), Collecting telemetry data privately (Microsoft)
  Class presentation
  
  
• [Apr 6: Lecture 19]
  Differential privacy III: the shuffle model.
  References: shuffle model III, shuffle model IV
  Additional references: shuffle model I, shuffle model II, shuffle model V
  Class presentation
  
  
• [Apr 8: Lecture 20]
  Protocols for differential privacy and differentially private protocols.
  References: Simultaneously solving how and what, differentially private access patterns, differentially private PSI
  Additional references: Computational differential privacy, distributed noise generation
  Class presentation
  
  
• [Apr 13: Lecture 21]
  Distributed private data collection and machine learning.
  References: private aggregation I, private aggregation II, Prio
  Additional references: Honeycrisp, open problems in federated learning
  Class presentation
  
  
• [Apr 15: Lecture 22]
  Fully homomorphic encryption (FHE) and secure computation from FHE.
  References: Halevi survey, Barak notes
  Additional references: Guide to FHE, GSW, multi-key FHE
  Class presentation
  
  
• [Apr 20: Lecture 23]
  ZK proofs from secure computation.
  References: MPC-in-the-head (journal version), Jawurek et al., Frederiksen et al.
  Additional references: KKS, Limbo, Ligero, Ligero++, BooLigero, Wolverine
  Class presentation
  
  
• [Apr 22: Lecture 24]
  NIZK proofs.
  References: Katz lecture notes
  Class presentation
  
  
• [Apr 27: Lecture 25]
  (ZK-)SNARKs and related topics.
  References: QSPs and succinct NIZKs
  Additional references: Groth 2016, Bulletproofs, PLONK, Supersonic, Virgo, Spartan
  Class presentation
  
  
• [Apr 29: Lecture 26]
  Oblivious RAM.
  References: Goldreich-Ostrovsky, Path ORAM, revisiting square-root ORAM
  Additional references: oblivious data structures I, oblivious data structures II, oblivious data structures III, differential obliviousness I, differential obliviousness II
  Class presentation
  
  
• [May 4: Lecture 27]
  Secure computation in the RAM model. PIR.
  References: Gordon et al., Katz lecture notes
  Additional references: BubbleRAM, PIR with compressed queries, PIR with sublinear online time
  Class presentation
  
  
• [May 6: Lecture 28] -- guest lecture by Prof. Kartik Nayak
  Consensus and blockchain/SMR protocols.
  References: Constant-round authenticated broadcast, Sync HotStuff
  Class presentation
  
  
• [May 11: Lecture 29]
  DPFs and applications to PIR.
  References: function secret sharing I, function secret sharing II, homomorphic secret sharing
  Class presentation
  
  
• [May 14: Final exam due]
  The final exam will be a take-home exam. It is available on Canvas, and is due by 10AM on May 14.
  

Additional references