In Semester 1, 2018-2019, I will be teaching CS 6111: Foundations of Cryptography.

Administrative Information.

When and Where.

Classes are held on Wednesday 3:25-4:40 pm and Friday 2:00 pm - 3:15 pm. Location: CSB 36.

Office Hours and Teaching Assistants.

The teaching assistants for the course are listed below. Monday 2-4 pm are the office hours, held in the PACE lab. I do not hold fixed office hours but will be happy to meet you anytime, just drop me an email!


This course requires mathematical maturity, you should be comfortable with the language of proofs. Knowledge of algorithms, theory of computing (i.e. familiarity with reductions), some algebra and probability theory is required. The course will be self contained for the most part but you should be familiar with the tools and techniques used in theoretical computer science.


Policies and Grades.

Collaboration is encouraged but you must write up solutions on your own. You must also write the names of all the people you discussed the problem with. In case you find material that will help you in solving some problems, you should mention the source in your writeup. Class participation will also be taken into account when assigning grades.
I expect all students to behave according to the highest ethical standards. Any cheating or dishonesty of any nature will result in failing the class.

Lecture Notes and Handouts.

Lecture Summaries.

The course will follow the outline of this previous offering.

Reading Material and References.

Background Reading: This blog by Ryan O'Donnell and this follow-up discussion contains a nice discussion of average case hardness, in particular Impagliazzo's worlds. Here is a discussion on basing cryptography on NP-hard problems by Scott Aaronson. This Wikipedia entry is also good to read. Here is a formal discussion of Shannon's lower bound for perfect security, section 1.3 of this contains another.

While we will not follow any particular text, the following are useful references.


Some useful handouts for probability, number theory and algebra are given below. Please refer to them on an "as needed" basis.
  1. Handout for basic probability by Luca Trevisan and another one by Boaz Barak.
  2. Handout for Algebra by Luca Trevisan.
  3. More technical introduction to number theory by D. Angluin.
  4. Very Basic and Basic number theory fact sheet by Dan Boneh.
  5. Computational Number Theory notes by Mihir Bellare.


Policy: You are encouraged to discuss problems but you are expected to fully understand and write down solutions on your own. Once the HW is returned, we will discuss solutions in class where I will randomly call upon students who got a homework problem correct to solve the problem on the board so that we all can understand and discuss the solution. So make sure you really know the solutions you write! The TAs will be watching for copied answers. If any copying is detected then you will earn a zero in ALL homework assignments. I will not discuss or bend this rule. No late submissions will be accepted unless in extreme situations.