W4261 Introduction to Cryptography: Fall 2025 Lecture Summaries

Below are brief summaries written after each lecture, of what was covered, together with recommended readings (in some cases, when explicitly indicated, the readings are required). Readings refer by default to chapters from the required textbook, though sometimes may include pointers to other texts found on the readings page, or to handouts written by us. The material in class does not correspond exactly to the material in the textbook. Often the readings below contain significantly more details and proofs than covered in class. Conversely, class sometimes contains material that is not in the textbook (I'll try to indicate when this is the case).

You are (only) responsible for (all) the material taught in class, any readings explicitly marked below as required (even if not covered in class), and anything covered by our homework. It will be assumed that before each lecture you carefully go over the previous lecture and required readings (if any).

• Lecture 1 (9/4) Introduction to modern cryptography, overview of this class and logistics. Kerckhoffs' principle. Definition of private key encryption scheme syntax and correctness. Overview of some basic historical ciphers (Atbash, shift, substitution) and simple attacks (brute force/exhaustive search, frequency analysis). Motivation for rigorous definition of security and discussion of what secrecy for private key encryption should mean (assuring that the key is hard to guess or that the message is hard to guess are not sufficient for security; definition of secrecy should work for any message distribution or prior knowledge of the adversary). Definition of perfect secrecy. This definition captures the intuition that the ciphertext contains no new information about the message, or equivalently: for any two messages m and m', any possible ciphertext c is equally likely to be the encryption of m or m' (subject to a random key generation). The shift and stream ciphers do not satisfy perfect secrecy.
  Reading: Chapter 1


• Lecture 2 (9/9) Defined one-time-pad (OTP) encryption scheme, and proved that it satisfies correctness and perfect secrecy. Discussed several (interrelated) problems with OTP, related to security and efficiency. First, we showed that you cannot reuse the key for more than one message (we can define perfect secrecy for multiple messages, and show OTP does not satisfy it). We briefly mentioned that if we allow encryption schemes to be stateful, and use a new independent key for each message, then this can be overcome (but keeping state opens the door to more problems). Additionally, the key is as long as the message. We then proved that both these problems are not specific to OTP, but inherent: every perectly secret scheme must have a key space at least as large as the message space, and no scheme can satisfy perfect secrecy for more than one message (ie., no perfectly secret scheme allows for key reuse). We discussed motivation for our move to computational security. Intuitively, we want to require that any polynomial time (efficient) adversary cannot break security, except with negligile probability (we recalled the definition of negligible). We gave some high level comments and motivation, and next time we will see a formal, game-based definition.
  Reading: Chapter 2, 3.1
  If needed, you should brush up on asymptotic notation, ppt algorithms, and negligible functions (see 3.1.2 in textbook, as well as appendix A and other materials in the background section of the webpage, as needed.


• Lecture 3 (9/11) Defined EAV-security for a computational private-key encryption scheme (also known as indistinguishability in the presence of an eavesdropper or single ciphertext only attack). Noted that if we remove the restriction on the adversary's running time, and set the advantage to 0 (rather than negligible), this would become another equivalent definition of perfect secrecy. Outlined why proving that there exists a EAV-secure scheme would yield a prove that P ≠ NP, and thus is hard. Instead, we rely on well-studied complexity assumptions. We mentioned that we know how to construct EAV-secure encryption from other cryptographic primitives, and in fact there are many such primitives who are known to be equivalent (OWF, PRG, PRF, private key encryption, signature schemes, and many more) -- we will cover many of these in the class, starting right now with PRG. We motivated and defined pseudorandom generators (PRG). Gave some simple non-examples. Showed that for any G, any algorithm that can check whether a given string is in the range of G or not, can distinguish outputs of G from random. Thus, no PRG is secure against computationally unbounded adversaries (and if the check can be performed efficiently, G is not a PRG). This also implies that if PRG exist, P≠ NP.
  Reading: Chapter 3.2.1, 3.3


• Lecture 4 (9/16) Showed an example of a construction of a PRG from another PRG and how to prove its security. More generally discussed security reductions in cryptography. Gave a very brief overview of how PRGs are constructed, with no details (we will show these later, and at this point in class it's ok if you didn't follow these constructions). In particular, mentioned practical block-cipher based constructions, and an example of a construction based on a number theoretic assumption (DDH). Proved that if G is a PRG, then G(G(·)) is also a PRG. Our proof was based on the hybrid argument technique (and can be generalized for any poly number of applications). Showed that if there's a PRG with even one bit expansion, then there is a PRG with arbitrary polynomial expansion, which can generate one bit at a time (sometimes called a stream cipher). We claimed that if a PRG exists, then there exists a EAV-secure encryption scheme. We showed the construction (which is similar to OTP but uses a pseudorandom one-time pad).
  Reading: Chapter 3.3. The construction from one bit expansion to arbitrary expansion PRG is in Chapter 8.4.2 (the proof is not part of our material). The rest is included here for your information but you are not responsible for it at this point: Constructions of PRG are covered in the book in sections 7.1,7.2,and 8. The DDH-based PRG candidate is not in the textbook, but the assumption itself is definition 9.64.


• Lecture 5 (9/18) Proved that the construction we saw last time (pseudorandom OTP) satisfies EAV-security. This gives us a construction with short keys, but we discussed why this does not satisfy multiple-message security (the same key can only be used once). We discussed how this could be addressed with stateful encryption (also sometimes called stream cipher), but requiring state is problematic (and our definition of encryption scheme is stateless). Instead, we will see in the next lectures how we can construct an encryption scheme with stronger security, by using PRFs. Defined CPA-security for private key encryption. Noted that CPA-security implies security for multiple messages (ie key can be reused). Discussed why CPA security requires randomized encryption (no deterministic scheme can have CPA-security), and in fact each message should have super-polynomially many different encryptions under the same key.
  Reading: Chapter 3.3, 3.4


• Coming up soon (in case you want to read ahead): PRF, PRP, using these to construct CPA-secure encyrption (Chapter 3.5 and some of 3.6). We will also mention how PRF can be constructed from PRG (Chapter 8.5) and how to construct PRP from PRF (Chapter 8.6)

Back to Course Main Page