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
3 Sept 4 Sept
7 Sept - Labor day 8 Sept 9 Sept
Preliminaries II (notes)
  • Primitives: OWFs, PRGs, PRFs, PRPs
  • 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
15 Sept 16 Sept
PIR, extensions (notes)
17 Sept 18 Sept

HW 1 due at 5pm.

21 Sept
PIR, offline/online (notes)
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
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
6 Oct 7 Oct
MPC: Intro, definitions (notes) Readings
8 Oct 9 Oct
12 Oct - Indigenous Peoples' Day 13 Oct
Unexpected Tuesday class
Three-party computation (notes) Readings
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)
20 Oct 21 Oct
Linear PCPs (notes)
22 Oct 23 Oct
26 Oct
Succinct zero-knowledge proofs (notes) Readings
27 Oct 28 Oct
ZK proofs on secret-shared data (notes) Readings
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
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
10 Nov 11 Nov - Veterans Day 12 Nov 13 Nov

HW 5 due at 5pm.

16 Nov
Guest Lecture: Emily Stark (Google)
17 Nov 18 Nov
More on TLS (notes)
19 Nov 20 Nov
23-26 Nov: Thanksgiving vacation
30 Nov
Online anonymity (notes)
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)
10 Dec 11 Dec