Wk  Date  Lecture contents 
Reading 
1  01/04 
Introduction
 Welcome / organizational details
 What is this class about? (Examples)
 Introduction to MPC


 01/06 
TwoParty Computation & Garbled Circuits
 Security of twoparty computation
 Recap of symmetric encryption
 Protocol for AND


2  01/11 
Garbled Circuits & Oblivious Transfer
 Garbled Circuits
 Review of ElGamal encryption
 Oblivious Transfer (BellareMicali)


 01/13 
Optimizations for TwoParty Computation
 Precomputing OT
 OT Extension
 Reducing Garbled Tables (row reduction and free XOR)


3  01/18 
No Class (MLK day)


 01/20 
Optimized Garbling & PrivateSet Intersection
 Reducing Garbled Tables (row reduction and free XOR)
 DiffieHelllman Based PrivateSet Intersection
 Oblivious PRF and PSI via OT etension

 [Slides] (Sorry, annotations were lost!)
 M. Bellare, P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. ACM CCS, 1993
 Benny Pinkas, Thomas Schneider, Michael Zohner. Faster Private Set Intersection Based
on OT Extension. USENIX Security, 2015.
 Benny Pinkas, Thomas Schneider, Gil Segev, Michael Zohner. Phasing: Private set intersection using permutationbased hashing. In USENIX Security, 2015.
 Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, Ni Trieu. Efficient batched OPRF with applications to PSI. In ACM CCS, 2016.
 Benny Pinkas, Mike Rosulek, Ni Trieu, Avishay Yanai. SpOTLight: Lightweight Private Set Intersection from Sparse OT Extension. CRYPTO 2019
 Melissa Chase, Peihan Miao. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF. CRYPTO 2020

4  01/25 
Actively Secure 2PC
 Actively Secure OT
 Cutandchoose and Majority Selection
 Dealing with SelectiveAbort Attacks


 01/27 
MPC I
 Secret Sharing
 The GMW Protocol
 Beaver's Triples
 Introducton to SPDZ


5  02/01 
MPC II
 SPDZ protocol
 Commitment Schemes
 Shamir Secret Sharing


 02/03 
MPC III + FullyHomomorphic Encryption
 Shamir's secret sharing
 The BGW protocol
 The LWE Assumption


6  02/08 
FHE
 The GSW scheme
 Bootstrapping
 Application: PIR


 02/10 
MultiKey FHE
 From GSW to MultiKey FHE
 Tworound MPC from Multikey FHE


7  02/15 
No Class (President Day)


 02/17 
ZeroKnowledge Proofs
 Interactive Proofs
 Definition of ZeroKnowledge
 GMR's protocol for NP
 Proof of Knowledge and Schnorr's protocol


8  02/22 
NonInteractive ZeroKnowledge Proofs
 NIZK definition
 The hidden bit model
 Proving Hamiltonicity in the HBM
 From the HBM to NIZKs using trapdoor permutations


 02/24 
SNARKs I
 Linear Interactive Proofs and Linear PCPs
 LIPs from LPCPs
 Bilinear maps
 Constructions of SNARGs/SNARKs from LIPs


9  03/01 
SNARKs II
 R1CS and Qudratic Span Programs
 An LPCP/LIP for QSPs


 03/03 
SNARKs III
 PCPs
 Merkle Trees
 CS Proofs
 Polynomial Commitments
 IOP Definitions

[Slides] [Annotated]
Silvio Micali.
ComputationallySound Proofs
Eli BenSasson, Alessandro Chiesa, Nicholas Spooner. Interactive Oracle Proofs
E. BenSasson, A. Chiesa, M. Riabzev. N. Spooner. M. Virza, N. Ward. Aurora: Transparent Succinct Arguments for R1CS

10  03/08 
Paper Presentations I
 Presentation I: Covert Security (Ashrujit, Ji, Xihu) [Slides] [Paper]
 Presentation II: Accumulators (Hanjun, Chenzhi) [Slides] [Paper]


 03/10 
Paper Presentations II
 Presentation I: CONIKs and SEEEMless (Matthew, Sudheesh, Keanu) [Slides] [Paper 1] [Paper 2]
 Presentation II: SMT and SNARKs (Ellis, Luke) [Slides] [Paper]

