CAS CS538, Fall 2011: Cryptography
MCS B33, Tue,Thu 12:30pm  2:00pm
Course web page: http://www.cs.bu.edu/~canetti/f11crypto.htm
Instructor: Ran Canetti. Office Hours: Tue 24pm. Email:
canetti@bu.edu
Syllabus: The course will
provide an indepth 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 oneway
functions; hardcore 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
Prerequisites: 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:
Lecture notes:
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.
