General description

The last few years have seen the roll out of privacy-preserving systems for a wide range of goals that include analytics, digital credentials, contact tracing, ad-click measurement, federated machine learning, CSAM detection, abuse reporting, attestation, etc. These systems rely on fairly advanced cryptographic tools which, in turn, are the object of intense research. This class will cover recent advances in this space, and develop a sound understanding of the underlying cryptography.

This course will cover both theoretical foundations as well as efficient designs. We will study different cryptographic primitives, and then see how they are used in actual systems.

This class complements an earlier 599 class (from Winter 21) that dealt with generic tools to solve some of these problems (multi-party computation and zero-knowledge proofs). Here, we will explore tools that underly more ad-hoc (but also more practical) solutions to these problems.

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 is available in this free textbook


Grading

There will not be any graded homework. Students are expected to complete a paper reading project (in pairs) 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/refined as we proceed through the quarter. The program is organized around cryptographic functionalities, but we will cover real-world examples on the way.

WkDate Lecture contents Reading
0 9/28 Introduction
  • Welcome / organizational details
  • What is this class about? (Examples)
  • Brief review: Group theory and hardness assumptions
1 10/3 Interactive Proofs and Zero-knowledge
10/05 Zero-Knowldge Review
  • ZK proof for graph 3-coloring
  • Introduction to NIZKs and Fiat-Shamir
2 10/10 From Identification Schemes to Signatures
  • The random oracle model
  • Non-interactive proofs of knowledge in the ROM
  • Introduction to Schnorr signatures
10/12 Pairings & BLS
  • Schnorr signatures wrap up
  • BLS Signatures and Aggregation
  • Elliptic curves and pairings
3 10/17 Pairing-based signatures
  • BLS and its security
  • Threshold Signatures from BLS
  • Multi-signatures and aggregation
10/19 Blind Signatures & Anonymous Tokens
  • Wrap up: BLS Aggregation and Multi-signatures
  • Blind Signatures
  • Anonymous Tokens/PrivacyPass
4 10/24 Anonymous Credentials
  • Introduction to ACs
  • BB Signatures
  • BBS Signatures
10/26 Group Signatures
  • Wrap up: BBS credentials
  • BBS Group Signatures
5 10/31 Multi-party Computation (intro)
  • Defining security of two-party computation
  • Yao's protocol & Garbled Circuits
11/02 Private-set intersection
  • Oblivious Transfer & OT Extension
  • Oblivious PRFs and PSI
6 11/07 Private-Set Intersection
  • OT-based Protocols
11/09 Guest Lecture
Christopher Wood (Cloudflare)
711/14 Intro to Analytics & Differential Privacy
  • Models for private analytics
  • Differential privacy
  • Laplacian mechanism
  • Randomized response & local DP
  • The shuffle model
11/16 Secure Aggregation (Multi-server)
  • A review of additive secret sharing
  • Prio and SNIPs
8 11/21 Single-Server Aggregation
11/23 No class (Thanksgiving)
9 11/28 Distributed Point Functions
  • Function Secret Sharing
  • Construction of DPFs from any PRG
  • Verifiable DPFs
11/30 Applications of DPFs
  • Heavy Hitters & Incremental DPFs
  • Verifiable DPFs and Sketching
10 12/05 Private Information Retrieval I
  • Definition & Applications
  • Single-server constructions
  • Two-server constructions
  • Efficient PIR from DPFs / read-write PIR
12/12 Private Information Retrieval II (Note this class was moved to 12/12)
  • Pre-processing PIR
  • Offline/online PIR
  • Doubly-efficient PIR