---

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:

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

Wk	Date	Lecture contents	Reading
0	9/28	Introduction Welcome / organizational details What is this class about? (Examples) Brief review: Group theory and hardness assumptions	[Slides]
1	10/3	Interactive Proofs and Zero-knowledge	[Slides] [Slides (Annotated)] Lecture notes by Mihir Bellare Zero-knowledge Proofs of Knowledge for Group Homomorphisms
	10/05	Zero-Knowldge Review ZK proof for graph 3-coloring Introduction to NIZKs and Fiat-Shamir	[Slides] [Slides (Annotated)]
2	10/10	From Identification Schemes to Signatures The random oracle model Non-interactive proofs of knowledge in the ROM Introduction to Schnorr signatures	[Slides] [Slides (Annotated)] Another Look at Provable Security (N. Koblitz & A. Menezes) From Identification to Signatures, Tightly: A Framework and Generic Transforms (M. Bellare, B. Poettering, and D. Stebila) Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma (M. Bellare and G. Neven)
	10/12	Pairings & BLS Schnorr signatures wrap up BLS Signatures and Aggregation Elliptic curves and pairings	[Slides] [Slides (Annotated)] An Introduction to Pairing-based Cryptography (A. Menezes) Mathematics of Public Key Cryptography (S. D. Galbraith) - entire textbook! Short Signatures from the Weil Pairing (D. Boneh, B. Lynn, and H. Shacham) Pairings for Cryptographers (S. D. Galbraith, K. G. Paterson, and N. P. Smart)
3	10/17	Pairing-based signatures BLS and its security Threshold Signatures from BLS Multi-signatures and aggregation	[Slides] [Slides (Annotated)] Efficient threshold signature, multisignature and blind signature schemes based on the Gap-Diffie-Hellman-group signature scheme (A. Boldyreva) Compact Multi-Signatures for Smaller Blockchains (D. Boneh, M. Drijvers, and G. Neven) Stronger Security for Non-Interactive Threshold Signatures: BLS and FROST (M. Bellare, S. Tessaro, and C. Zhu)
	10/19	Blind Signatures & Anonymous Tokens Wrap up: BLS Aggregation and Multi-signatures Blind Signatures Anonymous Tokens/PrivacyPass	[Slides] [Slides (Annotated)] Privacy Pass: Bypassing Internet Challenges Anonymously (A. Davidson, I. Goldberg, N. Sullivan, G. Tankersley, F. Valsorda) A Fast and Simple Partially Oblivious PRF, with Applications (N. Tyagi, S. Celi, T. Ristenpart, N. Sullivan, S. Tessaro, and C. Wood) Private Click Measurement Trust Tokens STAR: Secret Sharing for Private Threshold Aggregation Reporting (A. Davidson, P. Synder, E.B. Quirk, J. Genereux, B. Livshits, H. Haddadi) DIT: De-Identified Authenticated Telemetry at Scale (S. Huang et al.)
4	10/24	Anonymous Credentials Introduction to ACs BB Signatures BBS Signatures	[Slides] [Slides (Annotated)] Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups (D. Boneh and X. Boyen)
	10/26	Group Signatures Wrap up: BBS credentials BBS Group Signatures	[Slides] [Slides (Annotated)] Short Group Signatures (D. Boneh, X. Boyen, H. Shacham) Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions (M. Bellare, D. Micciancio, B. Warinschi) Orca: Blocklisting in Sender-Anonymous Messaging (N. Tyagi, J. Len, I. MIers, T. Ristenpart)
5	10/31	Multi-party Computation (intro) Defining security of two-party computation Yao's protocol & Garbled Circuits	[Slides] [Slides (Annotated)] 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.
	11/02	Private-set intersection Oblivious Transfer & OT Extension Oblivious PRFs and PSI	[Slides] [Slides (Annotated)] Y. Ishai, J. Killian, K. Nissim, E. Petrank. Extending Oblivious Transfers Efficiently (CRYPTO '03)
6	11/07	Private-Set Intersection OT-based Protocols	[Slides] [Slides (Annotated)] 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
	11/09	Guest Lecture Christopher Wood (Cloudflare)	[Slides] STAR: Secret Sharing for Private Threshold Aggregation Reporting (A. Davidson, P. Synder, E.B. Quirk, J. Genereux, B. Livshits, H. Haddadi)
7	11/14	Intro to Analytics & Differential Privacy Models for private analytics Differential privacy Laplacian mechanism Randomized response & local DP The shuffle model	[Slides] [Slides (Annotated)] The Algorithmic Foundations of Differential Privacy (C. Dwork and A. Roth) RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response (U. Erlingsson, V. Pihur, and A. Korolova) Distributed Differential Privacy via Shuffling (Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, Maxim Zhilyaev) Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity (Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, Abhradeep Thakurta)
	11/16	Secure Aggregation (Multi-server) A review of additive secret sharing Prio and SNIPs	[Slides] [Slides (Annotated)] Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (H. Corrigan-Gibbs, D. Boneh) Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (D. Boneh, E. Boyle, H. Corrigan-Gibbs, N. Gilboa, Y. Ishai) Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares (S. Addanki, K. Garbe, E. Jaffe, R. Ostrovsky, A. Polychroniadou) Exposure Notification Privacy-preserving Analytics (ENPA) White Paper (Apple & Google)
8	11/21	Single-Server Aggregation	[Slides] [Slides (Annotated)] Practical Secure Aggregation for Privacy-Preserving Machine Learning (K. Bonawitz et al.) ACORN: Input Validation for Secure Aggregation (J. Bell, A. Gascon, T. Lepoint, B. Li, S. Meiklejohn, M. Raykova) Secure Single-Server Aggregation with (Poly)Logarithmic Overhead (J. Bell, K. A. Bonawitz, A. Gascon, T. Lepoint, M. Raykova)
	11/23	No class (Thanksgiving)
9	11/28	Distributed Point Functions Function Secret Sharing Construction of DPFs from any PRG Verifiable DPFs	[Slides] [Slides (Annotated)] Function Secret Sharing (E. Boyle, N. Gilboa, and Y. Ishai) Function Secret Sharing: Improvements and Extensions (E. Boyle, N. Gilboa, and Y. Ishai) Lightweight, Maliciously Secure Verifiable Function Secret Sharing (L. de Castro, A. Polychroniadou)
	11/30	Applications of DPFs Heavy Hitters & Incremental DPFs Verifiable DPFs and Sketching	[Slides] [Slides (Annotated)] Lightweight Techniques for Private Heavy Hitters (D. Boneh, E. Boyle, H. Corrigan-Gibbs, N. Gilboa, Y. Ishai)
10	12/05	Private Information Retrieval I Definition & Applications Single-server constructions Two-server constructions Efficient PIR from DPFs / read-write PIR	[Slides] [Slides (Annotated)] A survey on Private Information Retrieval (W. Gasarch) A Survey of Single-Database PIR: Techniques and Applications (R. Ostrovsky, W. E. Skeith III) 2-Server PIR with sub-polynomial communication (Z. Dvir, S. Gopi) Riposte: An Anonymous Messaging System Handling Millions of Users (H. Corrigan-Gibbs, D. Boneh, D. Mazieres) Communication–Computation Trade-offs in PIR (A. Ali, T. Lepoint, S. Patel, M. Raykova, P. Schoppmann, K. Seth, K. Yeo)
	12/12	Private Information Retrieval II (Note this class was moved to 12/12) Pre-processing PIR Offline/online PIR Doubly-efficient PIR	[Slides] [Slides (Annotated)] Reducing the Servers’ Computation in Private Information Retrieval: PIR with Preprocessing (A. Beimel, Y. Ishai, T. Malkin) Limits of Preprocessing for Single-Server PIR (P. Persiano, K. Yeo) Private Information Retrieval with Sublinear Online Time (H. Corrigan-Gibbs, D. Kogan) Single-Server Private Information Retrieval with Sublinear Amortized Time (H. Corrigan-Gibbs, A. Henzinger, D. Kogan) One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval (A. Henzinger, M. Hong, H. Corrigan-Gibbs, S. Meiklejohn, V. Vaikuntanathan) FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval (A. Davidson, G. Pestana, S. Celi) Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE (W. Lin, E. Mook, D. Wichs)