A two-semester course on Foundations of Cryptography

Oded Goldreich

Last given: 2004-05.

This course will be given again in 2008-09.

Foundations of Cryptography: Two-semester course (2008-09)

The course will take place on Tuesdays, 14-16, in Room 1.

Syllabus

The foundations of cryptography are the paradigms, approaches and techniques used to conceptualize, define and provide solutions to natural security concerns. The course will present some of these conceptual tools as well as some of the fundamental results obtained using them. The emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving several central cryptographic problems.

In the first semester we will focus on basic tools such as one-way functions, pseudorandomness and zero-knowledge proofs. These will be used, in the second semester, which will provide a rigorous treatment of three basic applications: Encryption, Signatures, and General Cryptographic Protocols.

The course will consist of 20 lectures, 10 in each semester, and will closely follow the presentation in my two-volume book on the Foundations of Cryptography. Participating students will be credited 1.5 points for each semester, where a pass grade will be given subject to submitting (light-weight) homework assignments that are marked as satisfactory.

This course has some overlap with the course introduction to complexity theory. Specifically, one-way functions, pseodorandom generators, and zero-knowledge proofs are covered in both courses, but the perspective and the actual contents are different.

The course assumes basic knowledge of algorithms and complexity. That is, it does not require more than familiarity with the notion of a probabilistic polynomial-time algorithm and with the class NP. This background material appears in Sec. 1.2 and Sec. 1.3 of the aforementioned book (drafts of this book are available HERE).

Back to homepage.