CAS CS548, Spring 2012: Cryptographic Protocols

SOC B67, Tue, Thu 2:00pm – 3:30pm

Instructor: Ran Canetti. Office hours: Tue 3:30-5pm. Email:

Syllabus: The course will provide an introduction to cryptographic protocols, reviewing some of the basic models, definitions, proof techniques and results. Familiarity with the foundations of cryptography (e.g. CAS CS538 or equivalent) will be expected. Here is a tentative list of topics, by week:

  • Week 1: Zero-Knowledge (ZK). ZK protocols for NP. Sequential composition. ZK in constant # of rounds.

  • Week 2: Impossibility for Black-Box 3 rounds ZK. The Barak Protocol.

  • Week 3: Non-interactive ZK (NIZK).

  • Week 4: Encryption secure against chosen ciphertex attacks (CCA) from NIZK.

  • Week 5: CCA secure encryption in the random oracle model.

  • Week 6: Signatures schemes from identification in the random oracle model.

  • Week 7: Concurrent ZK.

  • Week 8: Non-malleable commitments and ZK.

  • Week 9: Secure multi party computation (MPC): Introduction, the GMW protocol.

  • Week 10: The BGW protocol.

  • Week 11: Notions of security for MPC: Basic, Universally Composable (UC) security.

  • Week 12: UC security of the BGW protocol, on the security of the GMW protocol.

  • Week 13: UC commitments.

  • Week 14: UC multi party computation (the CLOS protocol).

Course requirements: There will be weekly problem sets (around 10 altogether). Each problem set is due in class the following week. You are encouraged to collaborate and consult external resources in solving the homework problems. However, you should write the solution on your own, and list all external resources and collaborators. For more details on the collaboration policy see the policy for the Fall 2010 class, which is available here. In addition, there will be a final exam. The final grade will consist of 70% homework grades and 30% final exam - but you have to pass the exam to pass the course.

Reading material: Oded Goldreich’s Foundations of Cryptography covers some of the material. The other material is covered mainly by research and survey papers. A list of papers relevant for each class will be given ahead of time.

Problem Sets:

Problem Set 1.