Introduction to Cryptography, Fall 2008
--------------------------------------------------------------

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.

Prerequisites:
---------------------

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.

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


-Class notes: Each week a group of students will prepare notes covering this week's class. Each student will participate in preparing at least one set of notes.

-Homework: 3-5 homework sets

-There will also potentially be 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
-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
-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