Cryptographic Systems for Protecting Privacy

6.893: Cryptographic Systems for Protecting Privacy

MIT – Fall 2020

Important information

About this course: This page has all of the details.
Time: Mondays and Wednesdays, 1:00pm - 2:30pm (Boston time)
Per MIT rules, the course will actually begin at 1:05pm and will end by 2:25pm.
Location: Zoom (see Piazza for the link)

Tentative Schedule

Note: The order of topics may change over the course of the semester, but I will try to keep the due dates of the problem sets fixed.

M	T	W	Th	F
Weeks 1-2: Reminder of the preliminaries
31 Aug	1 Sept	2 Sept Preliminaries I (notes) Course intro Merkle Puzzles Readings Background: Boneh-Shoup, Section 2.4 Merkle's original paper A modern take on Merkle Puzzles Katz's lectures notes on random oracles	3 Sept	4 Sept
7 Sept - Labor day	8 Sept	9 Sept Preliminaries II (notes) Primitives: OWFs, PRGs, PRFs, PRPs Readings Boneh-Shoup The other subsections in Chapter 4 have really nice reference material on PRPs/PRFs in practice. on PRPs (Section 4.1) and PRFs (Section 4.4). Goldreich If you have time and interest, it's worth browsing some of the other sections of this textbook. It's the canonical reference on these basic primitives. You will never go wrong by spending an hour or two with Goldreich. on GGM construction of PRF from PRG (Section 3.6).	10 Sept	11 Sept
Weeks 3-5: Hiding access patterns
14 Sept Private information retrieval (notes) Definition CKGS protocol: Multi-server setting PIR, single-server setting Readings Original PIR paper (journal version) Kushilevitz-Ostrovsky single-server PIR Gasarch's [slightly outdated] survey on PIR	15 Sept	16 Sept PIR, extensions (notes) PIR by Keywords Batch PIR — reducing computation (see Section 5 of the paper)	17 Sept	18 Sept HW 1 due at 5pm.
21 Sept PIR, offline/online (notes) Paper: Private Information Retrieval with Sublinear Online Time Dima's Eurocrypt talk on offline/online PIR	22 Sept	23 Sept Guest Lecture: Elette Boyle (IDC Herzliya) Function secret sharing Low-communication two-server PIR Simple PIR by keywords PIR for sum/range queries Reading: Function Secret Sharing (Section 1 only)	24 Sept	25 Sept
28 Sept More function secret sharing (notes) DPF from one-way functions Application: Private statistics Readings: Rest of FSS paper from last lecture. See also this paper with additional optimizations.	29 Sept	30 Sept Oblivious RAM I (notes) Motivation and applications Definitions, comparison with PIR "Square-root" construction Readings Original Goldreich-Ostrovsky paper. We will cover the material from Section 4. Larsen and Nielsen's ORAM lower bound	1 Oct	2 Oct HW 2 due at 5pm.
Weeks 6-10: Computing public functions of private data
5 Oct Oblivious RAM II (notes) Tree-based ORAMs Readings Path ORAM A simple ORAM	6 Oct	7 Oct MPC: Intro, definitions (notes) Readings Pragmatic MPC, Chapter 2.3 Goldreich, Chapters 7.1 and 7.5.1	8 Oct	9 Oct
12 Oct - Indigenous Peoples' Day	13 Oct Unexpected Tuesday class Three-party computation (notes) Readings Pragmatic MPC, Chapter 3.3, 3.4 Beaver's paper on MPC with preprocessing	14 Oct Guest Lecture: Susan McGregor (Columbia) Readings: Please see Piazza!	15 Oct	16 Oct HW 3 due at 5pm.
19 Oct MPC in practice (notes) Readings Students and Taxes: A Privacy-Preserving Study Using Secure Computation (PETS 2016) On Deploying Secure Computing: Private Intersection-Sum-with-Cardinality (Euro S&P 2020) Realizing private and practical pharmacological collaboration (Science) Deriving genomic diagnoses without revealing patient genomes (Science)	20 Oct	21 Oct Linear PCPs (notes) Readings Efficient arguments without short PCPs	22 Oct	23 Oct
26 Oct Succinct zero-knowledge proofs (notes) Readings Succinct Non-Interactive Arguments via Linear Interactive Proofs	27 Oct	28 Oct ZK proofs on secret-shared data (notes) Readings Popular article from BU on Boston Wage Gap Survey Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs	29 Oct	30 Oct HW 4 due at 5pm.
Week 10: Differential privacy
2 Nov Differential privacy, central model (notes) Benefits and drawbacks Laplace mechanism Application: U.S. Census Readings Dwork and Roth -- See Chapters 1 and 2 for background. Slides on the use of D.P. in the 2020 U.S. Census Issues Encountered Deploying Differential Privacy Disclosure Avoidance and the Census	3 Nov	4 Nov Guest Lecture: Jennifer Granick (ACLU)	5 Nov	6 Nov
Weeks 11-13: More differential privacy, End-to-end privacy-enhancing systems
9 Nov Differential privacy, local model (notes) Randomized response Applications: Surveys, Telemetry, RAPPOR Readings Google: RAPPOR Apple: Learning with Privacy at Scale Apple: Differential Privacy Overview Microsoft: Collecting Telemetry Data Privately Practical Locally Private Heavy Hitters - Recent scheme for collecting heavy hitters with differential privacy in the local model	10 Nov	11 Nov - Veterans Day	12 Nov	13 Nov HW 5 due at 5pm.
16 Nov Guest Lecture: Emily Stark (Google) Readings How HTTPS works About HTTP Public-Key Pinning Certificate Transparency: A Bird's-Eye View	17 Nov	18 Nov More on TLS (notes) Readings Nick Sullivan's overview of TLS 1.3 ekr's slides on TLS 1.3 RFC 7457: Known attacks on TLS (February 2015)	19 Nov	20 Nov
23-26 Nov: Thanksgiving vacation
30 Nov Online anonymity (notes) Readings The Dining Cryptographers Problem Untraceable electronic mail, return addresses, and digital pseudonyms Tor: The Second-Generation Onion Router	1 Dec	2 Dec Guest Lecture: Joe Calandrino (FTC)	3 Dec	4 Dec HW 6 due at 5pm.
Week 14: Bonus topics
7 Dec Bonus lecture I: Martin Hellman (Stanford) Readings: Please see Piazza!	8 Dec	9 Dec Bonus lecture II: Precomputation attacks (notes) Readings Hellman's time-memory trade-off Oechslin's "Rainbow Tables" Fiat and Naor's refined preprocessing algorithm	10 Dec	11 Dec