Introduction to Cryptography, Fall 2010
--------------------------------------------------------------

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.

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:
---------------------------------




-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.



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