CS 127 / 227 / CSCI-E 207 - Cryptography

Syllabus

Instructor: Boaz Barak

TL;DR: This is a fast paced course starting from the basics of cryptography and going all the way to advanced topics. Students that are willing to put in the work to keep up will be exposed to some of the most exciting and impactful intellectual advances of the last 40 years.

“Human ingenuity cannot concoct a cipher which human ingenuity cannot resolve.” Edgar Allan Poe, 1841

Cryptography - the art or science of “secret writing” - has been around for several millenia, and for almost all of that time Edgar Allan Poe’s quote above held true. Indeed, the history of cryptography is littered with the figurative corpses of cryptosystems believed secure and then broken, and sometimes with the actual corpses of those who have mistakenly placed their faith in these cryptosystems. Yet, something changed in the last few decades. New cryptosystems have been found that have not been broken despite being subjected to immense efforts involving both human ingenuity and computational power on a scale that completely dwarves the “crypto breakers” of Poe’s time. Even more amazingly, these cryptosystem are not only seemingly unbreakable, but they also achieve this under much harsher conditions. Not only do today’s attackers have more computational power but they also have more data to work with. In Poe’s age, an attacker would be lucky if they got access to more than a few ciphertexts with known plaintexts. These days attackers might have massive amounts of data- terabytes or more - at their disposal. In fact, with public key encryption, an attacker can generate as many ciphertexts as they wish.

These new types of cryptosystems, both more secure and more versatile, have enabled many applications that in the past were not only impossible but in fact unimaginable. These include secure communication without sharing a secret, electronic voting without a trusted authority, anonymous digital cash, and many more. Cryptography now supplies crucial infrastructure without which much of the modern “communication economy” could not function.

This course is about the story of this cryptographic revolution. However, beyond the cool applications and the crucial importance of cryptography to our society, it contains also intellectual and mathematical beauty. To understand these often paradoxical notions of cryptography, you need to think differently, adapting the point of view of an attacker, and (as we will see) sometimes adapting the points of view of other hypothetical entities. More than anything, this course is about this cryptographic way of thinking. It may not be immediately applicable to protecting your credit card information or to building a secure system, but learning a new way of thinking is its own reward.

 

Syllabus

In this fast-paced course, I plan to start from the very basic notions of cryptogrpahy and by the end of the term reach some of the exciting advances that happened in the last few years such as the construction of fully homomorphic encryption, a notion that Brian Hayes called “one of the most amazing magic tricks in all of computer science”, and indistinguishability obfuscators which are even more amazing. To achieve this, our focus will be on ideas rather than implementations and so we will present cryptographic notions in their pedagogically simplest form– the one that best illustrates the underlying concepts– rather than the one that is most efficient, widely deployed, or conforms to Internet standards. We will discuss some examples of practical systems and attacks, but only when these serve to illustrate a conceptual point.

Depending on time, I plan to cover the following notions:

Prerequisites

The main prerequisite is the ability to read, write (and even enjoy!) mathematical proofs. In addition, familiarity with algorithms, basic probability theory and basic linear algebra will be helpful. We’ll only use fairly basic concepts from all these areas: e.g. Oh-notation- e.g. $O(n)$ running time- from algorithms, notions such as events, random variables, expectation, from probability theory, and notions such as matrices, vectors, and eigenvectors. Mathematically mature students should be able to pick up the needed notions on their own.

No programming knowledge is needed. If you’re interested in the course but are not sure if you have sufficient background, or you have any other questions, please don’t hesitate to contact me.

Why is cryptography hard?

Cryptography is a hard topic. Over the course of history, many brilliant people have stumbled in it, and did not realize subtle attacks on their ciphers. Even today it is frustratingly easy to get crypto wrong, and often system security is compromised because developers used crypto schemes in the wrong, or at least suboptimal, way. Why is this topic (and this course) so hard? Some of the reasons include:

If cryptography is so hard, is it really worth studying? After all, given this subtlety, a single course in cryptography is no guarantee of using (let alone inventing) crypto correctly. In my view, regardless of its immense and growing practical importance, cryptography is worth studying for its intellectual content. There are many areas of science where we achieve goals once considered to be science fiction. But cryptography is an area where current achievements are so fantastic that in the thousands of years of secret writing people did not even dare imagine them. Moreover, cryptography may be hard because it forces you to think differently, but it is also rewarding because it teaches you to think differently. And once you pass this initial hurdle, and develop a “cryptographer’s mind”, you might find that this point of view is useful in areas that seem to have nothing to do with crypto.

Course policies

To succeed in this course you will need to do the following:

  1. Before the first lecture (or at least no later than the end of shopping week): do homework zero, review mathematical background, and read the introduction lecture notes.

  2. You should read fully and deeply the lecture notes before each lecture. This is absolutely essential, as I will not repeat in the lecture all the notes’ content. Rather, I will focus on the key conceptual notions and the points which students found most confusing, so please come prepared with questions!

  3. Every week you will need to do two online multiple-question quizzes on the lecture notes for next week, as well as a more significant problem set (“pset” for short a.k.a “homeworks”) on the current week’s material.

Communication:

All students must sign up for the Piazza board, and are responsible for following the board, including any notifications that are posted there. Contact information and office hours for all staff members are posted on the course website.

If you have any question that is not of a personal nature, we encourage you to post it on Piazza so that other students can also benefit from the answer. Please make sure not to reveal pset answers in your question.

Piazza etiquette

If you have a question of a general technical nature related to the material of this course, please make it a public question on Piazza, so others can benefit from the answer. If you are worried it might be silly, then you can post it anonymously. However, I encourage you to post it under your name: all of us - staff included - sometimes misunderstand things and get confused. Not hesitating to ask questions is crucial to learning. Also, part of your participation grade relies on your activity on Piazza. If you post anonymously, you can’t get credit for it.

If you have a pset related question that might reveal some of your thought process on working on it, then please post it privately first. If the staff thinks it’s appropriate we might ask you to make it public later. If you’re not sure whether a pset-related question should be public or private, then make it private and ask us.

In Piazza, as in any other interaction in this class, we expect all students and staff to be respectful and friendly, as is fit for a community that has a shared goal of learning. Keep Piazza questions technical and don’t use it to post anonymous complaints (e.g., “the course is too hard” or “Boaz’s good looks are distracting me from learning”). We will have weekly anonymous surveys to raise non-technical issues.

Student assignments:

Students should read each week the lecture notes for the next week. You should read the lecture notes fully and deeply. Feel free to discuss any points you find confusing with other students and staff, including on the Piazza board.

Every week will have two online multiple choice quizzes via Canvas on the lecture notes for the upcoming lectures. There will be no late days for the quizzes, but we will have bonus points for them.

Every week a problem set will be due. All problem sets must be submitted as typed PDF files through Gradescope. We recommend that the PDF is produced by Markdown, though other ways (such as LaTeX) to produce a similarly formatted PDF are also fine. We will provide markdown sources of the psets to make it easier.

A problem set is considered late by 1 day if it is submitted between one minute to 24 hours late. It is considered late by 2 days if it is submitted between 24 hours and one minute to 48 hours late. A problem set will not be accepted if it is submitted more than 48 hours late. Every student can use a total of 6 late days over the term for problem sets. You are responsible for keeping track of your late days. Whenever submitting a pset late you should add a line on the top of the first page declaring this. Understating your late days will be an honor code violation.

Mathematical writing is a special case of writing, and so we will grade answers for clarity and not only correctness. Graders are not required to guess your intention or to “decrypt” highly obtuse solutions. If you do not know the answer to a question, we encourage you to simply write “I don’t know”, and you will receive 15% of the credit for this question.

Falling behind:

If a student significantly falls behind in submitting assignments or quizzes, they may (after a warning) be excluded from the course. If you are starting to have difficulties in this course it is imperative that you come talk to me before you are so far behind that it is impossible to catch up. We want you to succeed in this course and are here to help you do so.

Grading policy:

This is an advanced course which is catered toward students that are deeply interested in the subject material and presumably care less about the precise grade calculation. My current plan is to have the grade computed according to the following ratios:

If you are not doing a final project:

  1. 10%: online quizzes
  2. 30%: weekly problem sets
  3. 60%: final exam

If you are doing a final project:

  1. 10%: online quizzes
  2. 30%: weekly problem sets
  3. 35%: final exam
  4. 25%: final project

If you take the graduate version of this course then you must do a final project. If you take the undergraduate version then it is your choice whether to do a final project or not, and your grade will be based on the best out of the two calculations.

All components will have bonus questions in them. Bonus in one component can not be carried over to one component. I may modify the final grade by up to one letter grade up or down based on participation in the course.

Collaboration policy and academic integrity:

You can read together with other students the lecture notes and discuss them (in fact I highly recommend that!), but you should work on the quiz alone. You can work together with at most one person on the problem set but you should not split the problems between you, but rather both of you should work on all questions together and both are responsible for knowing the results for all questions. You can talk at a high level (without sharing solutions or writeups) with other people in the class, but you should give credit for any ideas and write the names of people you talked to on the submissions. You should obviously work on the final exam on your own.

If you have any question whether a certain action violates the course policy, please don’t hesitate to us. Even if you already had done something that might have violated the policy, it is still much much better if you approach us than if we find out on our own.

Honor code

We expect all students to adhere to the Harvard honor code. Some examples of activities that violate academic integrity include:

  1. Copying another student’s answer in a quiz, problem set, midterm, or final.

  2. Not citing a person or resource that helped you in the problem set.

  3. Posting problem set questions or answers online, or sharing them with students that are not currently enrolled in this course.

  4. Searching online for answers for particular problem set questions. It is completely fine to find and use general resources online on the course material. You should however cite any resource you used in your answer.

  5. Searching online for answers for the online quizzes. You should only attempt the quiz after you have read the lecture notes fully, and the lecture notes themselves contain all information you need to answer it.

  6. Understating the amount of late days you used in the problem set declaration.

Note that if we suspect an honor code violation, it could take us time to investigate and verify it, and so you may only find out about the issue very late in the term, or even after it ends. If you are worried that you might have inadvertently violated the honor code, it’s always best to come to us and discuss this. If you are not sure if something is an honor code violation or not, please ask us!

Student well being:

Your well being is very important to us. If you have any concerns or issues in this course, please reach out to me (Boaz), the teaching fellows, your resident dean, or the Harvard counselling services. If you have a serious medical or other emergency, please have your resident dean contact the course instructor. We will try to accommodate you as much as possible. For extension students, please contact the instructor and/or the extension TFs directly.