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
.