A two-semester course on Foundations of Cryptography
Oded Goldreich
Last given in 2013-14 in a supervised reading format
(previously given in 2004-05, 2008-09, and 2010-11).
In a nutshell, cryptography means the study of systems that are easy
to use but hard to abuse.
Guidelines for self study are available HERE.
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.
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.
Format
The course will be based on my
two-volume book on the Foundations of Cryptography,
and will cover approximately half the material in that book.
Students will be expected to read 10-20 pages a week,
and to participate in a weekly meeting (of 1-2 hours).
Each meeting will consist of two parts.
In the 1st part, we will discuss the material read,
and I will answer questions and/or add clarifications.
In the 2nd part, I will motivate and/or provide an overview
for the material to be read in coming week.
(The students will get free access to an e-copy of the book;
in addition, hardcopies of the book will be lent upon request.)
Prerequsites and Credits
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).
Participating students will be credited 2 points for each semester,
where a pass grade will be given subject to submitting (light-weight)
homework assignments that are marked as satisfactory.
Back to homepage.