A generator that adds a single bit looks useless. Iterate it and you get as many bits as you like — but the security proof no longer follows in one step, because the output now comes from many calls and the assumption speaks about one. The hybrid argument is how you cross that gap, and it charges you a factor of ℓ to do it.
given G : {0,1}n → {0,1}n+1 · build Gℓ : {0,1}n → {0,1}ℓ
The construction is the obvious one, and it is worth having in front of you. Write G(s) = (s′, σ), splitting each call's n+1 bits into n bits of state to carry forward and one bit of output. Set s₀ = s, put (sj, σj) = G(sj−1) for j = 1 … ℓ, and output σ₁ σ₂ ⋯ σℓ. The seed stays n bits and the cost is ℓ calls.
Here is the theorem, and then the difficulty.
If G is a pseudorandom generator with one bit of stretch, then Gℓ is a pseudorandom generator, for any polynomial ℓ.
Suppose D distinguishes Gℓ's output from ℓ uniform bits with advantage ε. To contradict the assumption we need a distinguisher for G — for one call, on n+1 bits. But D wants ℓ bits produced by ℓ chained calls, and we are handed only one challenge string. There is no way to feed the challenge straight through: it is the wrong length and the wrong shape.
The hybrid argument resolves this by refusing to compare the two ends directly. It builds a chain of distributions from one end to the other, each differing from its neighbour by a single call to G, and shows that a gap across the whole chain forces a gap across some one link.
For i = 0 … ℓ, let Hi be the distribution on ℓ-bit strings given by: the first i bits uniform and independent, and the remaining ℓ − i bits produced by the construction started from a fresh uniform state.
H₀ is exactly Gℓ's output. Hℓ is exactly ℓ uniform bits. Everything in between is a partial swap.
walk the ladder · one sample from each Hi
Slide from 0 to ℓ and the string converts from fully generated to fully random, one position at a time. Nothing about G is being assumed yet — this is just a definition.
|Pr[D(H₀) = 1] − Pr[D(Hℓ) = 1]| = ε is precisely the statement that D breaks Gℓ. The triangle inequality spreads that across the links:
ε ≤ Σi=0ℓ−1 |Pr[D(Hi) = 1] − Pr[D(Hi+1) = 1]|
ℓ terms summing to at least ε, so by pigeonhole at least one term is at least ε/ℓ. Find that link and you have found a break of a single call to G.
Fix i and look at Hi beside Hi+1. Both begin with i uniform bits. Both end with the construction run from a fresh state. They disagree at exactly one position: in Hi, position i+1 is the bit output by one call to G; in Hi+1 it is a coin flip, and the state that continues the string is fresh rather than the one that call produced.
the two neighbours
That is a difference of exactly one application of G, which is the shape the assumption can speak about. Build the distinguisher.
build D′ yourself · each correct choice writes a line
If z = G(u) for uniform u. Then σ is a genuine output bit and s′ is the state that call produced, so continuing from s′ is continuing the same chain. The string D sees is distributed exactly as Hi.
If z is uniform. Then σ is a uniform bit and s′ is a uniform state independent of it, so the string is i+1 uniform bits followed by the construction from a fresh state — exactly Hi+1.
So D′'s advantage on G equals the gap across link i. Averaging over a uniformly chosen i gives advantage ε/ℓ. If ε is non-negligible and ℓ is polynomial, so is ε/ℓ — which is why the theorem needs ℓ polynomial and why the factor is not free.