Syllabus

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:

  • Part I: Introduction

    1. How do we define security for encryption? Arguably the most important step in breaking out of the “build-break-tweak” cycle that Poe's quote described has been the idea that we can have a mathematically precise definition of security, rather than relying on fuzzy notions, that allow us only to determine with certainty that a system is broken but never have a chance of proving that a system is secure .

    2. Perfect security and its limitations: Showing the possibility (and the limitations) of encryptions that are perfectly secure regardless the attacker's computational resources.

    3. Computational security: Bypassing the above limitations by restricting to computationally efficient attackers. Proofs of security by reductions.

  • Part II: Private Key Cryptography

    1. Pseudorandom generators: The basic building block of cryptography, which also provided a new twist on the age-old philosophical and scientific question of the nature of randomness.

    2. Pseudorandom functions, permutations, block ciphers: Block ciphers are the working horse of crypto.

    3. Authentication and active attacks: Authentication turns out to be as crucial, if not more, to security than secrecy and often a precondition to the latter. We'll talk about notions such as Message Authentication Codes and Chosen-Ciphertext-Attack secure encryption, as well as real-world examples why these notions are necessary.

    4. Hash functions and the “Random Oracle Model”: Hash functions are used all over in crypto, including for verifying integrity, entropy distillation, and many other cases.

    5. Building pseudorandom generators from one-way permutations (optional): Justifying our “axiom” of pseudo-random generators by deriving it from a weaker assumption.

  • Part III: Pubic key encryption

    1. Public key cryptography and the obfuscation paradigm: How did Diffie, Hellman, Merkle, Ellis even dare to imagine the possiblity of public key encryption?

    2. Constructing public key encryption: Factoring, discrete log, and lattice based systems: We'll discuss several variants for constructing public key systems, including those that are widely deployed such as RSA, Diffie-Hellman, and the ellyptic curve variants, as well as some variants of lattice based cryptosystems that have the advantage of not being broken by quantum computers, as well as being more versatile. The former is the reason why the NSA has advised people to transition to lattice-based cryptosystems in the not too far future.

    3. Signature schemes: These are the public key versions of authentication though interestingly are easier to construct in some sense than the latter.

    4. Active attacks for encryption: Chosen ciphertext attacks for public key encryption.

  • Part IV: Advanced notions

    1. Fully homomorphic encryption: Computing on encrypted data.

    2. Multiparty secure computation: An amazing construction that enables applications such as playing poker over the net without trusting the server, privacy preserving data mining, electronic auctions without a trusted auctioneer, electronic elections without a trusted central authority.

    3. Zero knowledge proofs: Prove a statement without revealing the reason to why its true.

    4. Quantum computing and cryptography: Shor's algorithm to break RSA and friends. Quantum key distribution. On “quantum resistant” cryptography.

    5. Indistinguishability obfuscation: Construction of indistinguishability obfuscators, the potential “master tool” for crypto.

    6. Practical protocols: Techniques for constructing practical protocols for particular tasks as opposed to general (and often inefficient) feasibility proofs.

    7. Cryptocurrencies: Hash chains and Merkle trees, proofs of work, achieving consensus on a ledger via “majority of cycles”, smart contracts, achieving anonymity via zero knowledge proofs.

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 very helpful. We'll use relatively simple topics from those areas. In particular, the mathematical notions we will use are:

  • Algorithms and complexity: Oh notations, basic algorithms, representing data as strings, representing computation by Boolean circuits.

  • Probability: Events, random variables, expectation, Chernoff bounds

  • Linear algebra: (Later in the course) Matrices, vectors, eigenvectors.

  • Group theory: (Later in the course) Modular arithmetic, finite commutative groups.

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:

  • To argue about the security of a cryptographic scheme, you have to think like an attacker. This requires a very different way of thinking than what we are used to when developing algorithms or systems, and arguing that they perform well.

  • To get robust assurances of security you need to argue about all possible attacks . The only way I know to analyze this infinite set is via mathematical proofs . Moreover, these types of mathematical proofs tend to be rather different than the ones most mathematicians typically work with. Because the proof itself needs to take the viewpoint of the attacker, these often tend to be proofs by contradiction and involve several twists of logic that take some getting used to.

  • As we'll see in this course, even defining security is a highly non trivial task. Security definitions often get subtle and require quite a lot of creativity. For example, the way we model in general a statement such as “An attacker Eve does not get more information from observing a system above what she knew a-priori” is that we posit a “hypothetical alter ego” of Eve called Lilith who knows everything Eve knew a-priori but does not get to observe the actual interaction in the system. We then want to prove that anything that Eve learned could also have been learned by Lilith. If this sounds confusing, it is. But it is also fascinating, and leads to ways to argue mathematically about knowledge as well as beautiful generalizations of the notion of encryption and protecting communication into schemes for protecting computation .

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 night of the second lecture): 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. In addition to the lecture notes, you might find it useful to look at some of the textbooks listed in the home page. Our presentation will not directly follow any of those books, but when content is covered in the books it is likely to be presented there in more polished forms.

  4. Every week you will need to do two online multiple-question quizzes on the upcoming lecture notes, 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 Ed 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 Ed so that other students can also benefit from the answer. Please make sure not to reveal pset answers in your question.

Discussion board 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 Ed, 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 Ed. 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 Ed, 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 Ed 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”).

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 Ed board.

Every week will have two online multiple choice quizzes on the lecture notes for the upcoming lectures. There will be no late days for the quizzes, but to get a perfect grade on that component it will be enough to get an average of 75% of the points.

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.

In addition to those, students could do a final project and take scribe notes of one of the lectures.

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. The grade rubric might change, but the tentative plan is to have the grade computed according to the following ratios.

If you are not doing a final project:

  1. 10%: participation and reading
  2. 50%: weekly problem sets
  3. 40%: final exam

If you are doing a final project:

  1. 10%: participation and reading
  2. 30%: weekly problem sets
  3. 30%: final project
  4. 30%: final exam

If you are taking the graduate version, you must do a final project. If you are taking the undergrad version of this course, you can choose whether to do a final project or not. 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 are capped at 100% and cannot be carried over to other components. I may modify the final grade by up to one letter grade up or down based on participation in the course.

Collaboration and academic integrity:

Collaboration is highly encouraged in this course. We welcome you to form study groups, read the lecture notes together, share relevant resources you found online, and talk about the concepts in this course. However, there is a certain component of learning that is only achieved through the process of thinking deeply on a problem and (figuratively!) “banging your head against the wall”. So, for the problem sets themselves, you should follow the collaboration policy closely and make sure you “own your solutions”. If you get stuck on a problem set question, ask questions on the discussion board or come to office hours. However, keep in mind that we do not expect you to solve every single pset question, and as long as you give it a good try, you will learn from the process, which is ultimately the most important thing.

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 or sharing your answers for a quiz, problem set, midterm, or final. Brainstorming on problem set questions with other students is OK, sharing written solutions is not.

  2. Discussing problem sets with anyone except a current student in the course or a member of the teaching team.

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

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

  5. Using problem set solutions from previous offerings of this course.

  6. 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.

  7. Searching online for answers for the online quizzes. You should only attempt the quiz after you have read the text fully, and the text itself contain all information you need to answer it.

  8. 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!

Lecture attendance (non extension students only). I expect all non extension students to attend all lectures. If this policy is a problem then please let me know.

Falling behind:

If you are starting to have difficulties in this course it is imperative that you come talk to us (the instructor or the TF's) 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!

Student well being:

Your physical and mental 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 Harvard services such as Counseling and Mental Health Services (phone: 617-495-2042 (on business hours), 617-495-5711 (all other times), see also Let's Talk), the confidential peer counselling program Room 13 (phone: 617-495-4969), and the Beuro of Study Council (phone 617-495-4969).

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.

If you have a health condition that affects your learning or classroom experience, please let me know as soon as possible. Please also share with me any letter you have from the AEO so we can provide the appropriate accommodations.

Diversity, inclusion and belonging

My goal is to create a learning environment that supports a diversity of thoughts, perspectives and experiences, and honors your identities (including race, gender, class, sexuality, socioeconomic status, religion, and ability). I (like many people) am still in the process of learning about diverse perspectives and identities. If something was said in class (by me or anyone else) that made you feel uncomfortable, please talk to me about it. If you feel like your performance in the class is being impacted by your experiences outside of class, please don’t hesitate to come and talk with me. As a participant in offline and online course discussions, you should also strive to honor the diverse perspectives of your classmates and teaching staff. (Credit: based on the statement of Dr. Monica Linden at Brown University.)