Topics in Cryptography

Warning: This is the Spring 2018 course website.
The latest CS355 website is online here.


Syllabus

Date Topic and Readings
Problem Set 1 (due Friday, April 13 at 5pm via Gradescope).
Problem Set 2 (due Friday, April 27 at 5pm via Gradescope).
Problem Set 3 (due Friday, May 11 at 5pm via Gradescope).
Problem Set 4 (due Friday, May 25 at 5pm via Gradescope).
Problem Set 5 (due Friday, June 8 at 5pm via Gradescope).

You must use LaTeX to write up your problem set. You must use the provided template to typset your assignment.
Foundations of Cryptography
April 2
(David)
Topics (Lecture Notes)
  • Logistics and administration
  • Symmetric primitives: one-way functions (OWFs), pseudorandom generators (PRGs), and pseudorandom functions (PRFs)
  • The Blum-Micali PRG and hybrid arguments
Readings
April 4
(Henry)
Topics (Lecture Notes)
  • Random-oracle model
  • RSA full-domain hash signatures
Readings
Cryptographic Protocols
April 9
(Sam)
Topics (Lecture Notes)
  • Interactive proof systems
  • Zero-knowledge (simulation-based definitions)
Readings
April 11
(David)
Topics (Lecture Notes)
  • Proofs of knowledge
  • Sigma protocols
Readings
April 13 Problem Set 1 Due at 5pm via Gradescope.
April 16
(Henry)
Topics (Lecture Notes)
  • Non-interactive zero-knowledge
  • Fiat-Shamir heuristic
Readings
April 18
(Sam)
Topics (Lecture Notes)
  • Oblivious transfer (OT) and Yao's garbled circuits
Readings
April 23
(David)
Topics (Lecture Notes)
  • Shamir secret sharing
  • Beaver triples and MPC in the preprocessing model
Readings
April 25
(Henry)
Topics (Lecture Notes)
  • From MPC to zero-knowledge proofs (MPC-in-the-head)
Readings
April 27 Problem Set 2 Due at 5pm via Gradescope
Post-Quantum Cryptography
April 30
(Sam)
Topics (Lecture Notes)
  • The short integer solutions (SIS) problem
  • SIS Hash Function
Readings
May 2
(Sam)
Topics (Lecture Notes)
  • Lattice signatures
  • The learning with errors (LWE) problem
  • Regev encryption
Readings
May 7
(David)
Topics (Lecture Notes)
  • Fully homomorphic encryption (FHE)
Readings
May 9
(Sam)
Topics (Lecture Notes)
  • Alternatives to LWE for post-quantum cryptography
Readings
May 11 Problem Set 3 Due at 5pm via Gradescope
Applications
May 14
(Henry)
Topics (Lecture Notes)
  • Real-world cryptanalysis: Infineon attack
Readings
May 16
(Sam)
Topics (Lecture Notes)
  • Elliptic curve cryptography
  • Introduction to Pairings
Readings
May 21
(David)
Topics (Lecture Notes)
  • More applications of pairings-based cryptography: short signatures, identity-based encryption, broadcast encryption
Readings
May 23
(David)
Topics (Lecture Notes)
  • Linear probabilistically checkable proofs (linear PCPs)
  • Succinct non-interactive argument (SNARG) systems
Readings
May 25 Problem Set 4 Due at 5pm via Gradescope
May 28 No class: Memorial Day holiday
May 30
(Henry)
Topics (Lecture Notes)
  • Private computation of aggregate statistics
  • Proofs on secret-shared data
Readings
June 4
(David)
Bonus lecture: program obfuscation (Lecture Notes)
June 6
(Henry)
Bonus lecture: cryptanalysis (Lecture Notes)
June 8 Problem Set 5 Due at 5pm via Gradescope