Computer Science
Courant Institute

Introduction to Cryptography

CSCI-GA 3210-001

Fall 2018

Announcements

Homework assignments

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

Some Information

Lectures

Mondays 11:00am-12:50pm WWH 512
Instructor

Oded Regev
Office hours

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

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.
Requirements
 Active participation in class, homework assignments, final exam
Prerequisites
 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.

Schedule

Date Class Topic
Sep 10 Introduction, Perfect Secrecy. Lectures 1+2 of Peikert, Lecture 1 of Dodis, Section 1.3 of Pass-Shelat.
Sep 17 Solving HW0 and HW1 (including proof of Shannon's Theorem). Number theory.
Sep 24 One-way functions (and collections thereof). Examples of one-way functions (multiplication and subset sum). Weak one-way functions. Weak OWFs to strong OWFs (statement and informal discussion). Informal discussion of indistinguishability and pseudorandom generators.
Oct 1 HW3 Q1 & Q5. Weak OWFs to strong OWFs (the proof). More examples of OWFs: Subset sum (as collection and as function following HW3 Q2); Rabin's function and Rabin's permutation. Application of OWFs to password storage.
Oct 9 Indistinguishability. Pseudorandom generators. Expanding PRGs.
Oct 15 Blum-Micali PRG. Hard-core bits. Overview of Goldreich-Levin.
Oct 22 Goldreich-Levin. Pseudorandom functions: motivation and definition.
Oct 29 Constructing Pseudorandom functions.
Nov 5 Pseudorandom permutations and Luby-Rackoff; symmetric key encryption, definitions of security and constructions.
Nov 12 Public key encryption; Trapdoor one-way permutations.
Nov 19 Diffie-Hellman protocol and ElGamal cryptosystem. Authentication security definition.
Nov 26 Information theoretic construction of MAC. Computational construction of MAC using PRF. Expanding input of MACs using CRHF or almost universal hash functions.
Dec 3 Authenticated encryption. Digital Signatures.
Dec 10 Lattice-based cryptography
Dec 17 Final exam