Computer Science
Courant Institute

Introduction to Cryptography

CSCI-GA 3210-001

Fall 2015

Announcements

Homework assignments

Work is graded based on correctness, clarity, and conciseness. All solutions must be typeset in Latex, following the templates provided, and submitted electronically (send both TeX and PDF). Only submit work that you believe is correct; if you cannot solve a problem completely, you will get significantly more credit if you clearly identify the gaps in your solution. We recommend starting any longer solution with an informal yet accurate proof summary that describes the core idea. You are expected to read all the hints before the following class. Collaboration and consultation with external material is allowed, but must be declared for each question. The final exam will be based on homework questions.

For hints and further reading, use the Hint-o-matic.

Some Information

Lectures

Mondays 11:00am-12:50pm WWH 517
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
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 14 Introduction, Perfect Secrecy. Number theory. Lectures 1+2 of Peikert, Lecture 1 of Dodis, Section 1.3 of Pass-Shelat.
Sep 21 (Proof of Shannon's Theorem) Finishing number theory. One-way functions (and collections thereof). Weak one-way functions.
Sep 28 Examples of one-way functions. A bit on going from weak to strong OWFs. Weak OWFs to strong OWFs. Informal discussion of indistinguishability and pseudorandom generators.
Oct 5 Collections of one-way functions. More examples of OWFs. Application of OWFs to password storage.
Oct 13 Indistinguishability. Pseudorandom generators. Expanding PRGs.
Oct 19 Blum-Micali PRG. Hard-core bits. Goldreich-Levin; Pseudorandom functions: motivation and definition
Oct 26 Constructing Pseudorandom functions
Nov 2 Pseudorandom permutations and Luby-Rackoff; symmetric key encryption, definitions of security and constructions
Nov 9 Finishing symmetric key encryption; public key encryption
Nov 11 Trapdoor one-way permutations; Diffie-Hellman protocol and ElGamal cryptosystem. Authentication (model only)
Nov 23 Semantic security of PKE. Authentication security definition and info theoretic construction.
Nov 30 Computational construction of MAC using PRF. Expanding input of MACs using CRHF or almost universal hash functions.
Dec 7 Authenticated encryption. Digital Signatures. Zero Knowledge
Dec 9 Lattice-based cryptography (bonus class)
Dec 14 Final exam