Foundations of Cryptography - Winter 2003/4

Instructor: Moni Naor 

Grader: Guy Rothblum

When:     Thursday 14:00--16:00
Where:    Ziskind 1

DESCRIPTION:   Cryptography deals with methods for protecting the privacy, integrity and functionality of computer and communication systems. The goal of the course is to provide a firm foundation to the construction of such methods. In particular we will cover topics such as notions of security of a cryptosystem, proof techniques for demonstrating security and cryptographic primitives such as one-way functions and trapdoor permutations. .

PREREQUISITES: Students are expected to be familiar with algorithms, data structures, probability theory, and linear algebra, at an undergraduate level. No prior cryptography course will be assumed.

METHOD OF EVALUATION: There will be around twelve homework assignments and a final test. Homework assignments should be turned in on time (usually two weeks after they are given)! Try and do as many problems from each set. You may (and are encouraged to) discuss the problems with other students, but the write-up should be individual.

Exam : The exam will be in class.

BIBLIOGRAPHY: There is no textbook for the course. A lot of relevant material is available in 

• Oded Goldreich, Foundations of Cryptography, Cambridge, 2001.

HOMEWORK:

• Homework 1. ps
• Homework 2. ps
• Homework 3. ps
• Homework 4. ps
• Homework 5. ps
• Homework 6. ps
• Homework 7 (due Jan 8th). ps
• Homework 8 (due Jan 15th). ps
• Homework 9 (due Jan 22nd). ps
• Homework 10 (due Jan 29th). ps

HANDOUTS:

• Lecture 1: Identification, Entropy and One-way functions. pps
• Lecture 2: One-way functions: essential for identification, examples, from weak to strong. pps
• Lecture 3: Universal one-way functions, multiple identifications, One-way functions on their iterates, the Rabin functions examples, from weak to strong. pps
• Lecture 4: Universal hashing and authentication. pps
• Lecture 5: one-time signatures and one-way hashing. pps
• Lecture 6: One-way hashing from one-way permutations. Existentially unforgeable signature schemes. pps
• Lecture 7: Cryptography in the bounded space world pps
• Lecture 8: Existentially unforgeable signature schemes from UOWHF. Encryption. Beginning of pseudo-random generators pps
• Lecture 9: Hardcore predicates, Goldreich Levin Theorem. pps
• Lecture 10: Applications of the Goldreich Levin theorem, Constructions of Pseudo-Random Generators, Pseudo-Random Functions. pps
• Lecture 11: Constructions of Pseudo-Random Functions, Pseudo-Random Permutations. pps
• Lecture 12: Pseudo-Random Permutations pps. Notes on Luby-Rackoff Revisited ps
• Lecture 13: semanic Security and Indistinguishability of Encryptions. constructions. pps.