Topics in Cryptography

Course Schedule

Specific topics and suggested readings are subject to change as the quarter progresses.

Date Topic and Readings
Foundations of cryptography
Monday, March 28
(Alex)
[notes]

Topics:

  • Logistics & Course Overview
  • Merkle Puzzles

Readings:

Wednesday, March 30
(Alex)
[notes]

Topics:

  • Relationship between symmetric primitives: OWFs, PRGs, PRFs, block ciphers
  • Blum-Micali PRG construction
  • Goldreich-Goldwasser-Micali (GGM) PRF construction

Readings:

Monday, April 4
(Wilson)
[notes]

Topics:

  • Commitment schemes
  • The random oracle model

Readings:

Cryptanalysis
Wednesday, April 6
(Neil)
[notes]

Topics:

  • GCD attack on RSA keys
  • Infineon attack

Readings:

Friday, April 8 Problem Set 1 due at 5pm via Gradescope
Monday, April 11
(Alex)
[notes]

Topics:

  • Generic d-log attacks: Baby-Step Giant-Step, Pollard Rho, Shoup’s lower bound
  • A non-generic attack: Index calculus

Readings:

Elliptic-curve cryptography
Wednesday, April 13
(Wilson)
[notes]

Topics:

  • Introduction to elliptic curves

Readings:

Monday, April 18
(Wilson)
[notes]

Topics:

  • Pairings-based cryptography: 3-party key-exchange, short signatures, hashing to elliptic curves

Readings:

Zero knowledge proofs
Wednesday, April 20
(Alex)
[notes]

Topics:

  • Interactive proofs
  • Zero knowledge

Readings:

Friday, April 22 Problem Set 2 due at 5pm via Gradescope
Monday, April 25
(Wilson)
[notes]

Topics:

  • Sigma protocols

Readings:

Wednesday, April 27
(Neil)
[notes]

Topics:

  • Non-interactive zero-knowledge
  • Fiat-Shamir heuristic

Readings:

Monday, May 2
(Alex)
[notes]

Topics:

  • Succinct Non-interactive Arguments (SNARGs) from PCPs
  • Polynomial commitments
  • Arithmetic circuits and constraints

Readings:

Wednesday, May 4
(Wilson)
[notes]

Topics (Lecture Notes):

  • Polynomial Commitment + IOP = SNARG * mini-protocols: polynomial equality, vanishing polynomials, and univariate sum-check * Marlin-Lite: a SNARG for R1CS-SAT

Readings:

Friday, May 6 Problem Set 3 due at 5pm via Gradescope
Multi-party computation
Monday, May 9
(Alex)
[notes]

Topics:

  • Oblivious transfer
  • Two-party computation: Yao’s garbled circuits

Readings:

Wednesday, May 11
(Neil)
[notes]

Topics:

  • Secret-sharing
  • Multi-Party Computation

Readings:

Monday, May 16
(Neil)
[notes]

Topics:

  • Private Information Retrieval

Readings

Wednesday, May 18
(Alex)
[notes]

Topics:

  • Differential privacy

Readings: Two great surveys:

Friday, May 20 Problem Set 4 due at 5pm via Gradescope
Lattice cryptography
Monday, May 23
(Neil)
[notes]

Topics:

  • The learning with errors (LWE) problem
  • Regev encryption

Readings:

Wednesday, May 25
(Wilson)
[notes]

Topics:

  • Fully homomorphic encryption (FHE), part 1

Readings:

Monday, May 30
(--)
Memorial Day: no class
Wednesday, June 1
(Wilson)
[notes]

Topics:

  • Fully homomorphic encryption (FHE), part 2
  • Course wrap-up

Readings:

Friday, June 3 Problem Set 5 due at 5pm via Gradescope