Foundations of Cryptography (Spring 2008)

Error correcting codes are combinatorial objects that allow sending and recovering messages transmitted through noisy channels. Error correcting codes have many applications in both theory and practice in computer science. This class gives an

A key idea in modern cryptography is to try and design protocols that are secure against polynomial time adversaries (rather than all adversaries). This relaxed notion of security allows to implement many amazing tasks. (To give just one example we can consider two players playing poker over the phone without the help of a trusted party). In the course we will develop the basic machinery that allows such protocols with emphasis on precise definitions and rigorous proofs.

This course complements the course "introduction to cryptography" and students are allowed (and encouraged) to take both courses.


In the end of the semester there will be a home assignment. Following the home assignment, I may decide to conduct an oral exam (to make sure that students indeed prepared the solutions).

In addition during the semester I will give 2-3 exercises. The exercises are not mandatory and their purpose is for students to check that they follow the material.

Course material:

The material in the course is mostly covered in the following book (that is available in several copies in the library)


Some of the material can be found in lecture notes of a course by Yehuda Lindell from Bar-Ilan University.

Every week I will upload a (very brief) summary of the subjects that were covered.

Lecture 1 : Introduction

Lecture 2 : One-way functions

Lecture 3 : Hard core bits and the Goldreich-Levin theorem

Lecture 4 : Hard core bits and the Goldreich-Levin theorem (continued)

Lecture 5 : Statistical Indistinguishability, Computational Indistinguishability and Pseudorandomness

Lecture 6 : A construction of PRGs from any OWP.

Lecture 7 : Interactive proof systems and ZK

Lecture 8 : A ZK proof for every language in NP

Lecture 9 : More on ZK

Lecture 10 : Misc.

Home assignment

The home assignment can be downloaded here. Any updates will appear below.