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


1  10/3 
Interactive Proofs and Zeroknowledge


 10/05 
ZeroKnowldge Review
 ZK proof for graph 3coloring
 Introduction to NIZKs and FiatShamir


2  10/10 
From Identification Schemes to Signatures
 The random oracle model
 Noninteractive 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 
Pairingbased signatures
 BLS and its security
 Threshold Signatures from BLS
 Multisignatures and aggregation


 10/19 
Blind Signatures & Anonymous Tokens
 Wrap up: BLS Aggregation and Multisignatures
 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: DeIdentified Authenticated
Telemetry at Scale (S. Huang et al.)

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 
Multiparty Computation (intro)
 Defining security of twoparty computation
 Yao's protocol & Garbled Circuits


 11/02 
Privateset intersection
 Oblivious Transfer & OT Extension
 Oblivious PRFs and PSI


6  11/07 
PrivateSet Intersection

 [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 permutationbased 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. SpOTLight: 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)


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 PrivacyPreserving
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 (Multiserver)
 A review of additive secret sharing
 Prio and SNIPs

 [Slides] [Slides (Annotated)]
 Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (H. CorriganGibbs, D. Boneh)
 ZeroKnowledge Proofs on SecretShared Data via Fully Linear PCPs (D. Boneh, E. Boyle, H. CorriganGibbs, N. Gilboa, Y. Ishai)
 Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares (S. Addanki, K. Garbe, E. Jaffe, R. Ostrovsky, A. Polychroniadou)
 Exposure Notification Privacypreserving Analytics (ENPA)
White Paper (Apple & Google)

8  11/21 
SingleServer 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
 Singleserver constructions
 Twoserver constructions
 Efficient PIR from DPFs / readwrite PIR

 [Slides] [Slides (Annotated)]
 A survey on Private Information Retrieval (W. Gasarch)
 A Survey of SingleDatabase PIR:
Techniques and Applications (R. Ostrovsky, W. E. Skeith III)
 2Server PIR with subpolynomial communication
(Z. Dvir, S. Gopi)
 Riposte: An Anonymous Messaging System
Handling Millions of Users (H. CorriganGibbs, D. Boneh, D. Mazieres)
 Communication–Computation Tradeoffs 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)
 Preprocessing PIR
 Offline/online PIR
 Doublyefficient 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 SingleServer PIR (P. Persiano, K. Yeo)
 Private Information Retrieval
with Sublinear Online Time (H. CorriganGibbs, D. Kogan)
 SingleServer Private Information Retrieval
with Sublinear Amortized Time (H. CorriganGibbs, A. Henzinger, D. Kogan)
 One Server for the Price of Two: Simple and Fast SingleServer Private Information Retrieval (A. Henzinger, M. Hong, H. CorriganGibbs, S. Meiklejohn, V. Vaikuntanathan)
 FrodoPIR: Simple, Scalable, SingleServer 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)
