General description

This course will focus on two families of cryptographic tools: Multi-party computation (MPC) and zero-knowledge proofs (ZKPs). MPC enables a set of mutually distrustful parties to carry out a joint computation on their private data which only reveals the final output of the computation -- in particular, no further information about the data is ever leaked. ZKPs are used to prove a statement to a verifier, without revealing anything more beyond the validity of this statement.

These tools are cornerstones in the design of privacy-preserving systems, e.g., in solutions for private machine learning and data analytics, for private outsourced storage, as well as in privacy-preserving cryptocurrencies.

This course will cover both theoretical foundations as well as efficient designs.

Covered materials (tentative). Security definitions and trust models for secure MPC, oblivious Transfer, OT Exension, Garbled Circuits, Private Set Intersection, Secret Sharing, Fully-homomorphic encryption, Private Information Retrieval, Oblivious RAM, Function/homomorphic secret sharing, Zero-knowledge basics, Non-interactive Zero-knowledge, SNARKs.

Required background. The class is open to students with theoretical background as well as to students with applied interests who want to use these tools. A basic understanding of cryptography is necessary, but a graduate-level cryptography class is not required. (Contact the instructor if in doubt.)


There is no mandatory textbook. Reading materials will be posted throughout the class. Hower, the following are good references about basic cryptography: A good overview on secure multi-party computation (from an appleid viewpoint) is available in this textbook (available for free!)


There will not be any graded homework. Students are expected to complete a paper reading project (in groups) by the end of class (approx. 85% of grade). Participation will also be graded (approx. 15%). Note: due to somewhat unpredictable enrollment numbers, the exact implementation of this will be finalized during week one depending on the sizes of groups.


This is a tentative schedule meant to give an overview of the topics we are going to cover. It will be expanded as we proceed through the quarter.

WkDate Lecture contents Reading
1 01/04 Introduction
  • Welcome / organizational details
  • What is this class about? (Examples)
  • Introduction to MPC
01/06 Two-Party Computation & Garbled Circuits
  • Security of two-party computation
  • Recap of symmetric encryption
  • Protocol for AND
2 01/11 Garbled Circuits & Oblivious Transfer
  • Garbled Circuits
  • Review of ElGamal encryption
  • Oblivious Transfer (Bellare-Micali)
01/13 Optimizations for Two-Party Computation
  • Pre-computing OT
  • OT Extension
  • Reducing Garbled Tables (row reduction and free XOR)
3 01/18 No Class (MLK day)
01/20 Optimized Garbling & Private-Set Intersection
  • Reducing Garbled Tables (row reduction and free XOR)
  • Diffie-Helllman Based Private-Set Intersection
  • Oblivious PRF and PSI via OT etension
4 01/25 Actively Secure 2PC
  • Actively Secure OT
  • Cut-and-choose and Majority Selection
  • Dealing with Selective-Abort 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 + Fully-Homomorphic Encryption
  • Shamir's secret sharing
  • The BGW protocol
  • The LWE Assumption
6 02/08 FHE
  • The GSW scheme
  • Bootstrapping
  • Application: PIR
02/10 Multi-Key FHE
  • From GSW to Multi-Key FHE
  • Two-round MPC from Multi-key FHE
7 02/15 No Class (President Day)
02/17 Zero-Knowledge Proofs
  • Interactive Proofs
  • Definition of Zero-Knowledge
  • GMR's protocol for NP
  • Proof of Knowledge and Schnorr's protocol
8 02/22 Non-Interactive Zero-Knowledge 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. Computationally-Sound Proofs
  • Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner. Interactive Oracle Proofs
  • E. Ben-Sasson, 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]