Computer Science

Introduction to CryptographyCSCIGA 3210001 
Fall 2017 
Lectures

Mondays 11:00am12:50pm WWH 517 
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 11  Introduction, Perfect Secrecy. Number theory. Lectures 1+2 of Peikert, Lecture 1 of Dodis, Section 1.3 of PassShelat. 
Sep 18  (Proof of Shannon's Theorem) Finishing number theory. Oneway functions (and collections thereof). Weak oneway functions. 
Sep 25  Examples of oneway functions. Weak OWFs to strong OWFs. Informal discussion of indistinguishability and pseudorandom generators. 
Oct 2  Collections of oneway functions. More examples of OWFs. Application of OWFs to password storage. 
Oct 16  Indistinguishability. Pseudorandom generators. Expanding PRGs. 
Oct 23  BlumMicali PRG. Hardcore bits. GoldreichLevin; Pseudorandom functions: motivation and definition 
Oct 30  Constructing Pseudorandom functions 
Nov 6  Pseudorandom permutations and LubyRackoff; symmetric key encryption, definitions of security and constructions 
Nov 13  Finishing symmetric key encryption 
Nov 20  Public key encryption; Trapdoor oneway permutations; DiffieHellman 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  Latticebased cryptography (bonus class) 
Dec 18  Final exam 