CAS CS538, Fall 2016:   Cryptography


CAS B36,    Tue, Thu 3:30pm - 5pm

Course web page:

Instructor: Professor Ran Canetti.     Office Hours: Tue 5-7pm. Email:  

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 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: stream ciphers; semantic security; pseudorandom generators
  • Week 3: hard problems; one-way functions; hardness amplification
  • 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 hashing
  • Week 7: digital signatures
  • Week 8: trapdoor permutations; key exchange
  • Week 9: Public-key encryption: CPA, CCA, public key infrastructure
  • Week 10: commitments; coin tossing; interactive proofs
  • Week 11: zero knowledge; secure distributed computation
  • Week 12: delegation of computation; homomorphic encryption  
  • Week 13: functional encryption; program obfuscation 

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. CS330 is probably enough as well. 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.  You will also be expected to write proofs in a coherent and understandable way.


Class participation: Students are expected to show up to class and are encouraged to ask questions and participate actively in the class. The teaching will be interactive, using a white board, no slides. There will be no official class notes, but most of the material appears in multiple publications (see below).


Course requirements and final grade:  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 without looking at your fellow students solutions, and list all external resources and collaborators. In addition, there will be a final exam.  

The final grade will be calculated as  where  is the overall homework grade, F is the final grade, and is P is the participation grade. However, you must pass the final in order to pass the course.  Note: The points given to questions in each problem sets will usually sum up to more than 100. This means that you can get more than an overall 100 grade for the problem sets.  This extra grade will be rolled off to the rest of the grade.


Homework preparation and submission:    You are encouraged to collaborate with your fellow students and consult external resources in solving the homework problems.  Figuring out the problem sets together is more effective and more fun! However, you should write the solution on your own without looking at your fellow students solutions, and list all external resources and collaborators.


Solutions should be submitted electronically here:


|You can handwrite your solution, scan and submit, but typeset solutions will make the grader happier, which in turn may well make you happier. In particular, students are encouraged to use the LaTeX text editor to write solutions. If you do not yet know LaTeX then this is an excellent opportunity to learn, as it is the best software for preparing high quality scientific text. It is also an absolute must for graduate students.



Note: Failing to list collaborators in homework solutions, as well as looking at written solutions of  fellow student written before submission will be considered cheating and treated via the usual university channels for such cases.



Course administration and communication:  There is a piazza website for the course, at  Problem sets will be posted on the piazza website. All questions regarding the course, the teaching material, the problem sets etc. should be posted on the piazza board. Only personal issues should be communicated privately to the course staff. 



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, definitions, and often the instructional approach may differ from the lecture. See the syllabus of the class of fall 2015 for a more detailed description of the two books below, as well as several other useful ones.


Lecture notes:

Additional material: