Stretch a short key into a long pad, XOR it onto the message, and you have a cipher that no eavesdropper can break — provided the generator is sound. The proof is a reduction: any attacker on the cipher becomes, with a few lines of wrapping, a distinguisher for the generator.
k ← {0,1}n
c = G(k) ⊕ m
m = G(k) ⊕ c
The one-time pad needs a key as long as the message, which Shannon proved is unavoidable if you want perfect secrecy. Give up perfect secrecy for computational secrecy and the key can be short: use G(k) in place of the pad. Correctness is immediate, since XOR undoes itself.
encrypt and decrypt · n = 16 bit key, ℓ = 32 bit message
You cannot ask for "the attacker learns nothing" without saying how they would demonstrate learning something. The eavesdropping experiment makes it concrete: the attacker picks the two messages themselves, so they choose the most revealing pair they can think of, and they still must not be able to tell which was sent.
1. A outputs two messages m₀, m₁ of equal length.
2. A key k ← {0,1}n and a bit b ← {0,1} are drawn; A is given c = Enck(mb).
3. A outputs b′. The experiment is 1 if b′ = b.
Π is EAV-secure if every efficient A wins with probability at most 1/2 + negligible.
Play it. You choose the message pair, the page flips b in secret, and you see only the ciphertext. Two generators are offered: one built on SHA-256, and one that simply repeats the key. Against the second there is an attack, and finding it is the point of the exercise.
you are A · pick the pair, then guess which was encrypted
With c = (k ‖ k) ⊕ m, the two halves of c are equal exactly when the two halves of m are equal — the key cancels itself. So the pair m₀ = all zeros against m₁ = half zeros, half ones is decided by one comparison, with advantage 1/2. Note what the attack never needed: it never recovered k. Breaking encryption is not the same as recovering the key, and the definition is written to catch exactly this.
Now the theorem. Note the direction: we do not argue that the cipher is secure. We argue that if it is not, then the generator was not a generator.
If G is a pseudorandom generator, then Π with Enck(m) = G(k) ⊕ m has indistinguishable encryptions in the presence of an eavesdropper.
Suppose A wins the experiment with probability 1/2 + ε. Build A′, a distinguisher for G. It is handed a string w ∈ {0,1}ℓ that is either G(k) for a random k, or uniform, and it must say which. Inside, it runs A as a subroutine and simply plays the role of the encryption game.
build A′ yourself · each correct choice writes a line
If w = G(k). Then c = G(k) ⊕ mb is precisely a ciphertext of Π under a uniform key. A's view is identical to the real experiment, so it guesses correctly with probability 1/2 + ε, and A′ outputs 1 with that same probability.
If w is uniform. Then c = w ⊕ mb is a one-time pad encryption with a genuinely random pad, so c is uniform and carries no information about b at all. A cannot do better than chance, and A′ outputs 1 with probability exactly 1/2.
Subtracting, |Pr[A′(G(k)) = 1] − Pr[A′(r) = 1]| = ε. If ε is non-negligible then G is not a pseudorandom generator. The reduction runs A once and does a single XOR, so it is polynomial time — the second bullet on your slide.
measure it · runs the wrapped attacker in both worlds
| world | what w is | Pr[A′ outputs 1] |
|---|
the two worlds, as distributions
The same grid as the maps further down: six bits pick the column, six pick the row. The top row is the challenge w itself; the two below are the ciphertext c = w ⊕ mb that A is handed, for each value of b. Read down a column and you see what the reduction is doing to A.
The reduction says the scheme is exactly as good as its pad. So look at the pads. Draw a key at random, run the generator, and plot where the output lands; do it twenty thousand times and the shape of the distribution appears.
Thirty-two bits is 4.3 billion possible outputs, far too many to plot one per point. So the grid is a projection: six bits pick the column, six pick the row, and the other twenty are discarded. Each of the 4,096 cells therefore stands for 220 different strings, and the picture shows how the samples spread across those buckets rather than across the full space.
The logic runs one way only. If the projected picture is uneven, the real distribution is uneven — a projection of a uniform distribution is uniform, so any structure you can see is genuinely there. That direction is sound, and it is what makes the broken generators below convincing.
The reverse fails. An even picture proves nothing, because structure living entirely in the twenty discarded bits projects away to nothing. The bit-window control lets you change which six bits you look at, and one of the generators below is built to be invisible in one window and obvious in another.
two generators, same experiment
fair coins — the control
k ‖ k. The two halves of the pad are equal, so every point satisfies row = column and the whole distribution collapses onto the diagonal. Out of 4,096 cells it can reach 64. Switch to the ciphertext and the line moves — it becomes row = column ⊕ (top bits of mleft ⊕ mright) — but it is still a line. The message shifts the structure; it never destroys it.
Biased bits. No line, but the cloud is dragged toward the high corner, because strings with more ones are larger numbers. The structure here is uneven density rather than missing support, so a test that only hunts for repeats or collapsed dimensions would walk straight past it, while counting ones catches it at once. Different failures need different tests — which is why the definition quantifies over all of them.
SHA-256. An even wash across all 4,096 cells, with the cell-to-cell variation you would expect from throwing 20,000 balls into 4,096 boxes.
Low bits zeroed. In the top-bit window this reaches about 4,040 cells with a busiest cell around 15 — numbers indistinguishable from SHA-256's. It is nonetheless badly broken: three bits of every half are always zero, so seven eighths of the output space is unreachable. Switch the bit window to the bottom six and it collapses to a 64-cell lattice. The generator did not change; only the six bits you chose to look at did.
Now switch the plot to the ciphertext. The sound generator's picture does not change at all: XOR by a fixed message permutes a uniform distribution into another uniform one. The broken pictures move but keep their shape, and that is the whole content of the theorem in one image — the ciphertext distribution is the pad distribution, relabelled. A pad that is not uniform produces a ciphertext that is not uniform, and that is exactly what an eavesdropper is looking for.