Computer Science

Introduction to CryptographyCSCIGA 3210001 
Fall 2013 
For hints and further reading, use the Hintomatic.
Lectures

Mondays 5:00pm7:00pm, WWH 201 
Instructor 
Oded Regev 
Office hours

Mondays 3pm4pm, 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. 
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 9  Introduction, Perfect Secrecy. Number theory. Lectures 1+2 of Peikert, Lecture 1 of Dodis, Section 1.3 of PassShelat. 
Sep 16  (Proof of Shannon's Theorem) Finishing number theory. Oneway functions (and collections thereof). Weak oneway functions. Examples of oneway functions. 
Sep 23  Proof of weaktostrong oneway functions. Collections of oneway functions. Informal discussion of indistinguishability and pseudorandom generators. 
Sep 30  More examples of OWFs. Application of OWFs to password storage. Indistinguishability. Pseudorandom generators. Expanding PRGs. 
Oct 7  BlumMicali PRG. Hardcore bits. GoldreichLevin. 
Oct 21  Finishing GoldreichLevin; Pseudorandom functions 
Oct 28  Constructing Pseudorandom functions; pseudorandom permutations 
Nov 4  Finishing pseudorandom permutations and LubyRackoff; symmetric key encryption, definitions of security and constructions 
Nov 11  Finishing symmetric key encryption; public key encryption 
Nov 18  Trapdoor oneway permutations; DiffieHellman protocol and ElGamal cryptosystem. Authentication (model only) 
Nov 25  Semantic security of PKE. Authentication security definition and info theoretic construction. 
Dec 2  Computational construction of MAC using PRF. Expanding input of MACs. Digital Signatures. 
Dec 9  Zero Knowledge 
Dec 11  Latticebased cryptography 
Dec 16  Final exam 