0368-4162-01, Fall 2010:
Foundation of Cryptography
Instructors:
Ran Canetti | Schreiber 304 (in charge of the administrative issues of this semester, i.e., late submissions)
Iftach Haitner | Schreiber 20
The
course will provide a graduate-level introduction to Cryptography. The
goal is to give students a taste of the main concepts, abstractions and
algorithms, as well as the main tools and techniques. Some advanced
topics will also be touched upon. Open problems and research questions
will be mentioned along the way. Throughout, the course will alternate
between the foundational viewpoint and the applied one.
The
course "Cryptographic Protocols", given in the spring semester, will be
a direct continuation of this one.
The
exact syllabus will be determined as the semester proceeds, based on
the makeup of the class. A rough superset of the material covered
includes:
- Basic primitives: One way functions, Pseudorandom generators, Stream ciphers, Pseudorandom functions, Block ciphers, Collision resistant hash functions, Trapdoor permutations
- Basic protocols I: Message Authentication, Digital signatures, Encryption: Symmetric, asymmetric, Key Exchange, Secure Communication
- Basic protocols II: Commitment schemes, Coin tossing, Zero Knowledge, Oblivious Transfer, General function evaluation
- Advanced topics: General notions of security, protocol composition, Mechanized analysis, Cryptography and game theory, Program Obfuscation, New assumptions: Bilinear forms, lattice-based crypto
Announcements
Notes on Symmetric Encryption, taken this semster PDF
Basic complexity (the classes P, NP, BPP), basic probability. Some prior informal-level knowledge of cryptography (such as an undergraduate course) is recommended but not required.
- Homework: 3-5 homework sets
- Project: Each student will participate in a
project. Projects
will include scribing of selected classes, updating Wikipedia entries,
etc.
- There will also potentially be a final take home exam
Here are some guidelines for solutions.
You may find the following to be useful references (but beware that some of the notation, conventions, and definitions may differ slightly from lecture):
Books:- Jonathan Katz and Yehuda
Lindell. An
Introduction to Modern Cryptography.
- Oded Goldreich.
Foundations
of Cryptography.
- Ran Canetti.
Foundation of Cryptography (The 2008 course)
and On
Chernof and Chebichev bounds.
- Salil Vadhan.
Introduction to Cryptography.
- Luca Trevisan.
Cryptography.
- Yehuda lindell Foundations of Cryptography.