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
Tuesday, April 2
(Wilson)
[notes]

Topics:

  • Logistics & Course Overview
  • Relationship between symmetric primitives: from OWFs to PRGs, using Hardcore bits.

Readings:

Thursday, April 4
(Aditi)
[notes]

Topics:

  • Blum-Micali (PRG extension)
  • Goldreich-Goldwasser-Micali (PRF from PRG)

Readings:

Tuesday, April 9
(Wilson)
[notes]

Topics:

  • Luby-Rackoff (PRP from PRF)

Readings:

Thursday, April 11
(Trisha)
[notes]

Topics:

  • Commitment schemes

Readings:

Friday, April 12 Problem Set 1 due at 6pm via Gradescope
Cryptanalysis
Tuesday, April 16
(Aditi)
[notes]

Topics:

  • Infineon attack
    • Coppersmith’s Theorem

Readings:

Thursday, April 18
(Aditi)
[notes]

Topics:

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

Readings:

Elliptic-curve cryptography
Tuesday, April 23
(Wilson)
[notes]

Topics:

  • Introduction to elliptic curves

Readings:

Thursday, April 25
(Aditi)
[notes]

Topics:

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

Readings:

Friday April 26 Problem Set 2 due at 6pm via Gradescope
Zero knowledge proofs
Tuesday, April 30
(Trisha)
[notes]

Topics:

  • Interactive proofs
  • Zero knowledge

Readings:

Thursday, May 2
(Wilson)
[notes]

Topics:

  • Sigma protocols

Readings:

Tuesday, May 7
(Trisha)
[notes]

Topics:

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

Readings:

Thursday, May 9
(Wilson)
[notes]

Topics:

  • Succinct Non-interactive Arguments (SNARGs)
  • Polynomial commitments

Readings:

Friday, May 10 Problem Set 3 due at 6pm via Gradescope
Tuesday, May 14
(Trisha)
[notes]

Topics:

  • Polynomial Commitment + PolyIOP = SNARG
    • Polynomial IOPs
    • Plonkish Arithmetization
    • Plonk-Light: SNARG for Arithmetic Circuit-SAT

Readings:

Multi-party computation
Thursday, May 16
(Aditi)
[notes]

Topics:

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

Readings:

Tuesday, May 21
(Trisha)
[notes]

Topics:

  • Secret-sharing
  • Multi-Party Computation

Readings:

Thursday, May 23
(Wilson)
[notes]

Topics:

  • Private Information Retrieval

Readings

Friday, May 24 Problem Set 4 due at 6pm via Gradescope
Lattice cryptography
Tuesday, May 28
(Aditi)
[notes]

Topics:

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

Readings:

Thursday, May 30
(Trisha)
[notes]

Topics:

  • Fully homomorphic encryption (FHE)

Readings:

Tuesday, June 4
(Chelsea Komlo)

Topics:

  • Threshold Signatures (Guest Lecture)
  • Course wrap-up
Friday, June 7 Problem Set 5 due at 6pm via Gradescope