About

These are my notes for an undergraduate cryptography class (CS4830 at Cornell), with an emphasis on mathematical formality---definitions, theorems, and proofs---and perhaps on mathematical beauty as well, rather than on practical applications. They are largely inspired by a similar course taught by Shafi Goldwasser and Vinod Vaikuntanathan (6.875 at MIT), and the version of this class that I co-taught with Yael Kalai in 2019.

The notes are organized (roughly!) into chunks that can be covered in 75-minute lectures, though the notes often go into far more detail than I do in lectures.

Note that I'm not quite a cryptographer, but rather a theoretical computer scientist with an interest in cryptography. So, perhaps my writings on cryptography should be taken with a grain of salt---perhaps particularly when it comes to multiparty computation. With that said, I hope people find these to be useful. You might also consider looking at, e.g., Pass and shelat's course in cryptography, or simply Googling whatever cryptographic topic you're interested in.

Please let me know if you find any typos or mistakes, by e-mailing me. Thanks to the Spring 2023 CS4830 students for finding many typos in earlier versions of these notes.

Notes

• Introduction
  1. Introduction and Shannon's one-time pad.
  2. Computationally bounded adversaries, negligible functions, and a first look at semantically secure secret-key encryption and one-way functions.
  3. Some examples of one-way functions and some number theory background.
  4. Levin's universal one-way function!!
  5. Supplementary notes with some simple examples of proof by reduction involving one-way functions. (These are some additional notes that I provide to my students in order to provide much simpler examples than those covered in the main lecture notes---more similar to what they are likely to see in homework. So, these notes can safely be skipped, though they might be useful.)
• Journey from one-way functions to secret-key encryption!
  5. Hardcore bits, coin flipping, and commitments.
  6. The Goldreich-Levin Theorem (hardcore bits from any OWF)! (I usually do not actually present this result in class, as it's a bit difficult. These notes can safely be skipped.)
  7. Pseudorandom generators and the Blum-Micali construction.
  8. Fun with PRGs, and stream ciphers.
  9. Pseudorandom functions and the GGM construction.
  10. Secret-key encryption from PRFs.
• Authentication
  11. Message Authentication Codes (MACs).
  12. Signatures!
• Public-key encryption!!!
  1. Public-key encryption!! (These are combined lecture notes with roughly 5 lectures worth of material, including Rabin's trapdoor function, Diffie-Hellman key agreement, RSA, Goldwasser-Micali encryption, and Regev encryption.)
  2. Supplementary notes with some simple examples of reductions for primitives with interactive security games, like SKE, PKE, and signatures. (These are some additional notes that I provide to my students in order to provide much simpler examples than those covered in the main lecture notes---more similar to what they are likely to see in homework. So, these notes can safely be skipped, though they might be useful.)
  18. Fully homomorphic encryption!!!!!
• Zero-knowledge proofs!!
  19. Proof systems and zero-knowledge proofs!
  20. ZKPs for all of NP!!
• Multiparty computation (but mostly just two-party computation)
  21. Secret sharing.
  22. Introduction to two-party computation and oblivious transfer.
  24. The GMW protocol for 2PC.
  25. Yao's garbled circuits.
• Bonus lectures!
  26. Random oracles and oracle worlds