Computer Science

Introduction to CryptographyCSCIGA 3210001 
Fall 2018 
Lectures

Mondays 11:00am12:50pm WWH 512 
Instructor 
Oded Regev 
Office hours

Mondays 9:45am10: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. 
Date  Class Topic 
Sep 10  Introduction, Perfect Secrecy. Lectures 1+2 of Peikert, Lecture 1 of Dodis, Section 1.3 of PassShelat. 
Sep 17  Solving HW0 and HW1 (including proof of Shannon's Theorem). Number theory. 
Sep 24  Oneway functions (and collections thereof). Examples of oneway functions (multiplication and subset sum). Weak oneway 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  BlumMicali PRG. Hardcore bits. Overview of GoldreichLevin. 
Oct 22  GoldreichLevin. Pseudorandom functions: motivation and definition. 
Oct 29  Constructing Pseudorandom functions. 
Nov 5  Pseudorandom permutations and LubyRackoff; symmetric key encryption, definitions of security and constructions. 
Nov 12  Public key encryption; Trapdoor oneway permutations. 
Nov 19  DiffieHellman 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  Latticebased cryptography 
Dec 17  Final exam 