Foundation of Cryptography, Fall 2011

--------------------------------------------------------------
This is a a graduate-level introduction to the theoretical foundations of Cryptography. We'll study the basic cryptographic primitives (e.g., one-way functions and pseudorandom generators) while focusing on formal definitions and rigorous proofs. Some more advanced topics will be also touched upon.

Prerequisites:
---------------------
Basic complexity (the classes P, NP, BPP), basic probability. Some prior informal-level knowledge of cryptography, such as the undergraduate course 0369.3049, is recommended but not required.

This is a graduate course, where undergrads are encouraged to take 0369.3049. In some special cases, however, undergrads who got my personal permission can take the course.

Course requirements:
---------------------------------

• Homework: 3-5 homework sets
• A final exam

Syllabus:
-------------
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, Pseudorandom functions, 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