# CSCI-GA 3210-001

## Fall 2013

### Homework assignments

Work is graded based on correctness, clarity, and conciseness. All solutions must be typeset in Latex, following the templates provided, and submitted both in print and 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. 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 5:00pm-7:00pm, WWH 201 Instructor Oded Regev Office hours Mondays 3pm-4pm, 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.

### Schedule

 Date Class Topic Sep 9 Introduction, Perfect Secrecy. Number theory. Lectures 1+2 of Peikert, Lecture 1 of Dodis, Section 1.3 of Pass-Shelat. Sep 16 (Proof of Shannon's Theorem) Finishing number theory. One-way functions (and collections thereof). Weak one-way functions. Examples of one-way functions. Sep 23 Proof of weak-to-strong one-way functions. Collections of one-way 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 Blum-Micali PRG. Hard-core bits. Goldreich-Levin. Oct 21 Finishing Goldreich-Levin; Pseudorandom functions Oct 28 Constructing Pseudorandom functions; pseudorandom permutations Nov 4 Finishing pseudorandom permutations and Luby-Rackoff; symmetric key encryption, definitions of security and constructions Nov 11 Finishing symmetric key encryption; public key encryption Nov 18 Trapdoor one-way permutations; Diffie-Hellman 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 Lattice-based cryptography Dec 16 Final exam