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] (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 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 Actively Secure OT Cut-and-choose and Majority Selection Dealing with Selective-Abort Attacks	[Slides] [Annotated] Y. Lindell, B. Pinkas. An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries. EUROCRYPT 2007. C. Shen, a.shelat. Two-output Secure Computation With Malicious Adversaries. EUROCRYPT 2011. Y. Lindell. Fast Cut-and-Choose Based Protocols for Malicious and Covert Adversaries. CRYPTO 2013. Y. Huang, J. Katz, V. Kolesnikov, R. Kumaresan, A. Malozemoff. Amortizing Garbled Circuits. CRYPTO 2014. Y. Lindell, B. Riva. Cut-and-Choose Based Two-Party Computation in the Online/Offline and Batch Settings. CRYPTO 2014. P. Mohassel, M. Franklin. Efficiency Tradeoffs for Malicious Two-Party Computation. PKC 2006.
	01/27	MPC I Secret Sharing The GMW Protocol Beaver's Triples Introducton to SPDZ	[Slides] [Annotated] I. Damgard, V. Pastro, N.P. Smart, S. Zakarias. Multiparty Computation from Somewhat Homomorphic Encryption . CRYPTO 2012.
5	02/01	MPC II SPDZ protocol Commitment Schemes Shamir Secret Sharing	[Slides] [Annotated]
	02/03	MPC III + Fully-Homomorphic Encryption Shamir's secret sharing The BGW protocol The LWE Assumption	[Slides] [Annotated] G. Asharov, Y. Lindell. A Full Proof of the BGW Protocol for Perfectly-Secure Multiparty Computation C. Peikert. A Decade of Lattice Cryptography
6	02/08	FHE The GSW scheme Bootstrapping Application: PIR	[Slides] [Annotated]
	02/10	Multi-Key FHE From GSW to Multi-Key FHE Two-round MPC from Multi-key FHE	[Slides] [Annotated] P. Mukherjee and D. Wichs. Two Round Multiparty Computation via Multi-Key FHE. EUROCRYPT 2016
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	[Slides] [Annotated]
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	[Slides] [Annotated] Some lecture notes covering today's contents: Here and here
	02/24	SNARKs I Linear Interactive Proofs and Linear PCPs LIPs from LPCPs Bilinear maps Constructions of SNARGs/SNARKs from LIPs	[Slides] [Annotated] N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, O. Paneth. Succinct Non-Interactive Arguments via Linear Interactive Proofs J. Groth. On the Size of Pairing-based Non-interactive Arguments
9	03/01	SNARKs II R1CS and Qudratic Span Programs An LPCP/LIP for QSPs	[Slides] [Annotated] R. Gennaro, C. Gentry, B. Parno, M. Raykova. Quadratic Span Programs and Succinct NIZKs without PCPs B. Parno, J. Howell, C. Gentry, M. Raykova. Pinocchio: Nearly Practical Verifiable Computation
	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]