CAS CS538, Fall 2011: Cryptography

MCS B33, Tue,Thu 12:30pm - 2:00pm

Course web page: http://www.cs.bu.edu/~canetti/f11-crypto.htm

Instructor: Ran Canetti. Office Hours: Tue 2-4pm. Email: canetti@bu.edu

Syllabus: The course will provide an in-depth introduction to cryptography. The goal is to give students a taste of the main concepts, abstractions and algorithms, as well as the main .tools of the trade. and techniques. Throughout, the course will alternate between the foundational viewpoint and the applied one. Here is a tentative list of topics, by week:

• Week 1: overview of cryptography; perfect encryption
• Week 2: hard problems; one way functions; hardness amplification
• Week 3: stream ciphers, computational indistinguishability, pseudorandom generators
• Week 4: PRGs from one-way functions; hard-core predicates
• Week 5: block ciphers; pseudorandom functions and permutations
• Week 6: message authentication codes; collision resistant hash functions
• Week 7: digital signatures
• Week 8: semantic security; symmetric encryption
• Week 9: trapdoor permutations; key exchange
• Week 10: asymmetric encryption: CPA, CCA, public key infrastructure
• Week 11: the random oracle methodology for signatures and encryption
• Week 12: commitments; coin tossing; interactive proofs
• Week 13: zero knowledge; secure distributed computation
  
  

Pre-requisites: The only formal prerequisite is Probability Theory (CS237). Some knowledge of complexity theory, such as the notion of Turing machines and the classes P and NP is recommended. (If you took Theory of computation (CS332) you.re all set. If in doubt, contact the instructor.) Some informal prior knowledge in cryptography can be useful but is not required. Most importantly, the course requires some level of .mathematical maturity.: You will be expected to assimilate new mathematical concepts and complete on your own proofs that were not completely spelled out in class.

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 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: We will not follow any single textbook. Still, practically all the material that will be presented in class is covered by one or more of the resources listed below, as well as many others that are available online. Beware, however, that conventions, notations and definitions may differ from lecture. See the syllabus of the class of fall 2010 for a more detailed description of the two books below, as well as several other useful ones.

Books:

• Jonathan Katz and Yehuda Lindell.  An Introduction to Modern Cryptography.
• Oded Goldreich. Foundations of Cryptography.

Lecture notes:

• Ran Canetti. Introduction to Cryptography
• Leo Reyzin: Fundamentals of Cryptography
• Salil Vadhan: Introduction to Cryptography
• Luca Trevisan. Cryptography.
• Yehuda lindell Foundations of Cryptography.
• Mihir Bellare and Shafi Goldwasser: Lecture Notes on Cryptography
• Jonathan Katz: Introduction to Cryptography (undergraduate and graduate)
• Ronitt Rubinfeld: On Chernov and Chebichev bounds.

Problem Sets:

Problem Set 1.

Problem Set 2.
Problem Set 3.
Problem Set 4.
Problem Set 5.
Problem Set 6.
Problem Set 7.
Problem Set 8.
Problem Set 9.
Problem Set 10.