COMS E6261: Advanced Cryptography

Spring 2016: Minimalist Cryptography

General Information | Lecture Summaries | Homeworks | Readings | Class Requirements | Projects


(4/15) project presentation schedule has been posted.

Class-related News

General Information

Instructor: Tal Malkin, Office hours: Mondays 3:30-4:30pm in 514 CSB or by appointment.
Teaching Assistant: Lucas Kowalczyk, Office hours: Monday 4:30-5:30 in Data Science Institute (4th Floor Mudd) or by appointment.
Time & Place: Tue 10:10-12:00, 253 Engineering Terrace

Administrative Notes: This course can be used as a theory elective for the PhD program in computer science, as a track elective for MS students in the "Foundations of Computer Science" track or the "Computer Security" track, or as a track elective for undergraduates in the "Foundations" track. COMS E-6261 Advanced Cryptography focuses around a different topic, possibly with a different format, every time it is taught. The class can be repeated for credit.


COMS-4261 Introduction to Cryptography or COMS-W4236 Introduction to Computational Complexity or instructor approval. The most important prerequisite is mathematical maturity and comfort with rigorous definitions and proofs.

Course Description

The course will focus on selected cryptographic tools that can be based on one-way functions or weaker assumptions (including unconditional cryptography).

This theme could easily span several semesters, so we will not try to give an exhaustive treatment. Instead, we will study in depth a few results in different areas, and give an overview and pointers to other directions and applications. The specific topic selection will be biased by the interests of the instructor and the students taking the class, and will range from classic results from the 80s to cutting edge research papers. In all cases, we will take a rigorous theoretical approach (including precise definitions, theorem statements, and proofs). Example topics may include: zero knowledge proofs, secret sharing, secure multiparty computation, randomized encoding, circuit complexity of cryptographic primitives, barriers to basing cryptography on P not equal NP, and many other options.

Lecture Summaries

Below is a summary of what was covered in each class and related readings. The readings may not match exactly what was covered in class (e.g., the readings may provide expanded and more detailed treatment than what was given in class, or class may cover things that do not appear in the readings).


Homeworks will be posted here, and due at the beginning of class. No late homework please. The (few) problem sets are designed to make sure you understand the material, and may be challenging. You should not search for solutions on line (or anywhere else), but rather try to solve the problems on your own. I am happy to discuss homework problems with you and to give hints in office hours, and happy for you to discuss the problems with other students in the class, but these things should happen only after you spend a considerable amount of effort on solving the problems on your own. If you do discuss the problems, the actual solutions must still be written by yourself independently, and all your discussion partners should be listed. Even if I can't enforce these rules, I expect and trust that you will abide by them.


There is no required textbook for the class. Below are some recommended textbooks (all are available either on-line or through the library). Pointers to required and recommended readings for specific lectures will be posted above as the semester progresses.

Textbook most relevant to the class (in addition to research papers):

Other textbooks that can be used as reference (note there are some differences in notation and approaches among these): See some reading pointers for the lectures related to secure computation.

For high level slides and videos of tutorial talks on various crytpgoraphic areas, check the Bar-Ilan Winter Schools (every year starting 2011), and the 2015 Simons semester on Crypto (in particular the lectures in the Crypto Boot Camp). More detailed links to the above are given in section 2.7 and 2.8 of the projects page.

Grading and Requirements

The class requirements are as follows:

Academic Honesty

I expect that the primary goal of everyone in the class is to learn (I can imagine no other reason that you would be in this class). Hopefully this means that there will be no focus on grades (which I can tolerate but do not like), and no issues of dishonesty (which I absolutely will not tolerate).

As in every CS class, students are expected to adhere to the academic honesty policy of the CS department.