CSE 599: Cryptographic Protocols for Privacy-Preserving Computation (Winter 2021)

Instructor: Stefano Tessaro, tessaro(at)cs

Time and location: MW 1-2:20p, Over zoom (Meeting ID is accessible through Canvas - contact the instructor if there are any problems.)

Office hours: M 2:30-3:30p (Do inform me if you plan to come later, and not just stay after class). Or on appointment.

Dicussion platform: We will be using edstem. You should have received an invite, otherwise contact us for assistance.

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:

R. Pass and a. shelat. A Course in Cryptography (graduate level, focusing on theory)
M. Rosulek. The Joy of Cryptography (undergraduate level, broader scope)
O. Goldreich. The Foundations of Cryptography (a thorough and formal textbook on foundations.)
J. Katz and Y. Lindell. Introduction to Modern Cryptography (a textbook, graduate level)
D. Boneh and V. Shoup A Graduate Course in Applied Cryptography (a textbook, graduate level)
M. Bellare and P. Rogaway's lecture notes. Introduction to Modern Cryptography (lecture notes for a grad class, focus on practice-oriented provable security)

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.

Wk	Date	Lecture contents	Reading
1	01/04	Introduction Welcome / organizational details What is this class about? (Examples) Introduction to MPC	[Slides] [Annotated]
	01/06	Two-Party Computation & Garbled Circuits Security of two-party computation Recap of symmetric encryption Protocol for AND	[Slides] M. Bellare, VT. Hoang, P. Rogaway, Foundations of Garbled Circuits, ACM CCS 2012. Y. Lindell, B. Pinkas, A Proof of Security of Yao's Protocol for Two-Party Computation.
2	01/11	Garbled Circuits & Oblivious Transfer Garbled Circuits Review of ElGamal encryption Oblivious Transfer (Bellare-Micali)	[Slides] [Annotated]
	01/13	Optimizations for Two-Party Computation Pre-computing OT OT Extension Reducing Garbled Tables (row reduction and free XOR)	[Slides] [Annotated] Y. Ishai, J. Killian, K. Nissim, E. Petrank. Extending Oblivious Transfers Efficiently (CRYPTO '03) S. Zahur, M. Rosulek, D. Evans. Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates (EUROCRYPT '15)
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	[Slides] [Annotated] 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 permutation-based 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. SpOT-Light: 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
	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