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.
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
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 .
Perfect security and its limitations: Showing the possibility (and the limitations) of encryptions that are perfectly secure regardless the attacker’s computational resources.
Computational security: Bypassing the above limitations by restricting to computationally efficient attackers. Proofs of security by reductions.
Part II: Private Key Cryptography
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.
Pseudorandom functions, permutations, block ciphers: Block ciphers are the working horse of crypto.
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.
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.
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
Public key cryptography and the obfuscation paradigm: How did Diffie, Hellman, Merkle, Ellis even dare to imagine the possiblity of public key encryption?
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.
Signature schemes: These are the public key versions of authentication though interestingly are easier to construct in some sense than the latter.
Active attacks for encryption: Chosen ciphertext attacks for public key encryption.
Part IV: Advanced notions
Fully homomorphic encryption: Computing on encrypted data.
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.
Zero knowledge proofs: Prove a statement without revealing the reason to why its true.
Quantum computing and cryptography: Shor’s algorithm to break RSA and friends. Quantum key distribution. On “quantum resistant” cryptography.
Indistinguishability obfuscation: Construction of indistinguishability obfuscators, the potential “master tool” for crypto.
Practical protocols: Techniques for constructing practical protocols for particular tasks as opposed to general (and often inefficient) feasibility proofs.
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.
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.
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.
To succeed in this course you will need to do the following:
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.
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!
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.
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.
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.
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.
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.
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:
If you are doing a 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.
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.
We expect all students to adhere to the Harvard honor code. Some examples of activities that violate academic integrity include:
Copying another student’s answer in a quiz, problem set, midterm, or final.
Not citing a person or resource that helped you in the problem set.
Posting problem set questions or answers online, or sharing them with students that are not currently enrolled in this course.
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.
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.
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!
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.