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.)


Resources

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!)


Grading

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.


Schedule

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
01/27 MPC I
5 02/01 MPC II
02/03 Fully-Homomorphic Encryption
6 02/08 Multi-Key FHE and Two-Round MPC
02/10 Private Information Retrieval
7 02/15 Zero-knowledge Proofs for NP
02/17 NIZK I
8 02/22 NIZK II
02/24 SNARKs I
9 03/01 SNARKs II
03/03 SNARKs III
10 03/08 Paper Presentations I
03/10 Paper Presentations II