Lecture 1 · Tuesday 23 September 2025
Perfect secrecy
The first lecture fixes the method of the course and applies it to the strongest confidentiality guarantee. Perfect secrecy is defined, priced by Shannon's bound and achieved by the one-time pad.
Before ThisWhere the Course Starts
The course opens with the setting that all later lectures inherit: Alice sends a message to Bob over a channel that the eavesdropper Eve controls. The two honest parties share a secret key in advance. The first task is to make "secure" precise. The first answer is information-theoretic, with no bound on Eve's computing power.
This LectureWhat It Adds
The lecture introduces the method of modern cryptography: state a definition, propose a construction and prove that breaking the definition implies solving an assumed-hard problem. The adversary is probabilistic polynomial time (randomized, with runtime polynomial in the security parameter), success is negligible (too small to matter) and Kerckhoffs's principle puts all secrecy in the key. Perfect secrecy then requires that the ciphertext leave the message distribution unchanged, even for an unbounded Eve. Shannon's bound shows that any such scheme needs at least as many keys as messages. The one-time pad meets that bound with equality, while the two-time pad lab shows what key reuse reveals.
Study PlanWhat to Read, in Lecture Order
- Chapter 1 §1: Modern cryptography, and how it argues. The definition-construction-proof method, the security parameter (a number that sets key sizes and runtime budgets), negligible advantage (an attack edge too small to matter) and Kerckhoffs's principle (all secrecy rests in the key, even when the attacker knows the system).
- §2: Perfect secrecy, and why it costs too much. The definition, the posterior-equals-prior reading (the ciphertext tells Eve nothing new about the message) and Shannon's bound with its proof sketch.
- §3: The one-time pad. The construction, the proof of perfect secrecy and the two-time pad leak, with the lab encrypting two messages under one pad.
PracticeExercises for This Lecture
- Compute the One-Time Pad (OTP) posterior on $\bits^2$: the definition of perfect secrecy on a concrete ciphertext.
- Prove Shannon's bound: why the key space must cover the message space.
- Recover a message from two ciphertexts under one pad: the key cancels, so the plaintext relation remains.