Computer Science
|
Introduction to CryptographyCSCI-GA 3210-001 |
Fall 2017 |
| 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 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 Pass-Shelat. |
| Sep 18 | (Proof of Shannon's Theorem) Finishing number theory. One-way functions (and collections thereof). Weak one-way functions. |
| Sep 25 | Examples of one-way functions. Weak OWFs to strong OWFs. Informal discussion of indistinguishability and pseudorandom generators. |
| Oct 2 | Collections of one-way functions. More examples of OWFs. Application of OWFs to password storage. |
| Oct 16 | Indistinguishability. Pseudorandom generators. Expanding PRGs. |
| Oct 23 | Blum-Micali PRG. Hard-core bits. Goldreich-Levin; Pseudorandom functions: motivation and definition |
| Oct 30 | Constructing Pseudorandom functions |
| Nov 6 | Pseudorandom permutations and Luby-Rackoff; symmetric key encryption, definitions of security and constructions |
| Nov 13 | Finishing symmetric key encryption |
| Nov 20 | Public key encryption; Trapdoor one-way permutations; Diffie-Hellman 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 | Lattice-based cryptography (bonus class) |
| Dec 18 | Final exam |