Computer Science
Courant Institute

Introduction to Cryptography

CSCI-GA 3210-001

Fall 2017


Homework assignments

No programming is required in this course. Weekly written problem sets will be assigned. The final exam will consistent of a subset of these problems (possibly with very minor variations).

Some Information


Mondays 11:00am-12:50pm WWH 517

Oded Regev
Office hours

Mondays 9:45am-10:45am, WWH 303

Introduction to Cryptography, by Jonathan Katz and Yehuda Lindell. A good introductory book.
Foundations of Cryptography, Vol. 1 and 2 by Oded Goldreich. A comprehensive book for those who want to understand the material in greater depth.
Lecture notes by Yevgeniy Dodis, which we'll follow closely
Lecture notes by Chris Peikert
Lecture notes by Rafael Pass and Abhi Shelat.
Last year's course
My colleagues Thomas Vidick and Stephanie Wehner created an online EdX course on quantum cryptography.
Active participation in class, homework assignments, final exam
Students are expected to be comfortable reading and writing mathematical proofs, be at ease with algorithmic concepts, and have elementary knowledge of discrete math, number theory, and basic probability. No programming will be required for the course.


Date Class Topic
Sep 11 Introduction, Perfect Secrecy. Number theory. Lectures 1+2 of Peikert, Lecture 1 of Dodis, Section 1.3 of Pass-Shelat.
Sep 18 (Proof of Shannon's Theorem) Finishing number theory. One-way functions (and collections thereof). Weak one-way functions.
Sep 25 Examples of one-way functions. Weak OWFs to strong OWFs. Informal discussion of indistinguishability and pseudorandom generators.
Oct 2 Collections of one-way functions. More examples of OWFs. Application of OWFs to password storage.
Oct 16 Indistinguishability. Pseudorandom generators. Expanding PRGs.
Oct 23 Blum-Micali PRG. Hard-core bits. Goldreich-Levin; Pseudorandom functions: motivation and definition
Oct 30 Constructing Pseudorandom functions
Nov 6 Pseudorandom permutations and Luby-Rackoff; symmetric key encryption, definitions of security and constructions
Nov 13 Finishing symmetric key encryption
Nov 20 Public key encryption; Trapdoor one-way permutations; Diffie-Hellman protocol and ElGamal cryptosystem.
Nov 27 Authentication security definition and info theoretic construction.
Dec 4 Computational construction of MAC using PRF. Expanding input of MACs using CRHF or almost universal hash functions. Authenticated encryption.
Dec 11 Digital Signatures.
Dec 12 Lattice-based cryptography (bonus class)
Dec 18 Final exam