If $\mathcal A$ always outputs $gl(x,r)$, query $r = e^i$: $gl(x,e^i) = x_i$. That gives $n$ queries and all of $x$, contradicting one-wayness.

∎

Key identity: $gl(x,r)\oplus gl(x,r\oplus e^i) = x_i$ for any $r$.

Good inputs (Claim 6.14): by averaging, a set $S_n$ of at least $\frac\varepsilon2 2^n$ inputs $x$ has $\Pr_r[\mathcal A(f(x),r) = gl(x,r)]\ge\frac34 + \frac\varepsilon2$. Otherwise the overall success couldn’t reach $\frac34 + \varepsilon$. Fixing $x\in S_n$ leaves only $r$ random, so repeated trials are independent.

One bit: $r$ and $r\oplus e^i$ are each uniform (not independent). A union bound on failures gives $\le2(\frac14 - \frac\varepsilon2) = \frac12 - \varepsilon$, so both answers are right, and $x_i$ correct, with probability at least $\frac12 + \varepsilon$.

Amplify: take the majority over about $n/\varepsilon^2$ independent $r$‘s. Chernoff gives error at most $\frac1{2n}$ per bit. A union bound over $n$ bits gives all of $x$ with probability at least $\frac12$ on $S_n$, i.e. overall at least $\varepsilon/4$, which is non-negligible.

Why $\frac34$: below that, the two-query union bound gives no advantage.

∎

Problem: two queries, each right with probability only $\frac12 + \varepsilon$, can’t be combined. Fix: query $\mathcal A$ only on $r\oplus e^i$ and guess $gl(x,r)$ yourself, for many $r$ at once, cheaply.

Pairwise-independent $r$‘s from few seeds: pick $\ell = \lceil\log(2n/\varepsilon^2 + 1)\rceil$ uniform seeds $s^1,\ldots,s^\ell$ and set $r^I = \bigoplus_{i\in I}s^i$ for every nonempty $I\subseteq[\ell]$. That gives $m = 2^\ell - 1\approx2n/\varepsilon^2$ strings, each uniform and pairwise independent (for $I\ne J$, some seed is in exactly one of them).

Guess only $\ell$ bits: guess $\sigma^i = gl(x,s^i)$, all correct with probability $2^{-\ell}\gtrsim\varepsilon^2/4n$. By linearity, $gl(x,r^I) = \bigoplus_{i\in I}gl(x,s^i)$, so all $m$ guesses $\tau^I = \bigoplus_{i\in I}\sigma^i$ are then right.

Algorithm $\mathcal A'$: for each $i$, set $v^I_i = \tau^I\oplus\mathcal A(y, r^I\oplus e^i)$ and $x_i = \mathrm{majority}_I(v^I_i)$.

Analysis (Claim 6.18): with correct $\tau$‘s and $x\in S_n$, each indicator $X_I = [v^I_i = x_i]$ has mean at least $\frac12 + \frac\varepsilon2$, variance below $\frac14$, and the $X_I$ are pairwise independent. By pairwise-independent Chebyshev, $\Pr[\text{majority wrong}]\le\frac{\mathrm{Var}}{(\varepsilon/2)^2m} < \frac1{2n}$. A union bound over bits gives $x$ correct with probability at least $\frac12$.

Total: $\frac\varepsilon2\cdot\frac{\varepsilon^2}{4n}\cdot\frac12 = \frac{\varepsilon^3}{16n}$, which is non-negligible. This contradicts one-wayness.

∎

Suppose $D$ distinguishes $(f(s),hc(s))$ from uniform $(n+1)$-bit strings with advantage $\varepsilon$. Uniform is the same as $(f(s),\beta)$ for a random bit $\beta$, which is half $(f(s),hc(s))$ and half $(f(s),\overline{hc(s)})$. So $D$ separates $(f(s),hc(s))$ from $(f(s),\overline{hc(s)})$ with advantage $2\varepsilon$; say it outputs 1 more often on the former.

Predictor $\mathcal A(y)$: pick a random $\sigma$, run $D(y,\sigma)$, and output $\sigma$ if $D$ says 1, else $\bar\sigma$. Then

$$\Pr[\mathcal A = hc] = \tfrac12\Pr[D(f,hc) = 1] + \tfrac12\big(1 - \Pr[D(f,\overline{hc}) = 1]\big) = \tfrac12 + \tfrac12\cdot2\varepsilon$$

contradicting $hc$ being hard-core.

∎

Hybrids: $H^i$ is $i$ truly random bits followed by $p(n) - i$ bits generated from a fresh random seed. $H^0 = G(s)$ and $H^{p(n)}$ is uniform.

Distinguisher $D'$ for $G_1$, given $w\in\{0,1\}^{n+1}$: pick $i\leftarrow\{0,\ldots,p - 1\}$; output $i$ random bits, then $w$‘s last bit, then the generator’s output from seed $w_{[n]}$; run $D$ on the result.

• If $w = G_1(s)$, this is exactly $H^i$.
• If $w$ is uniform, it is exactly $H^{i+1}$.

The sum telescopes:

$$\big\lvert\Pr[D'(G_1(s)) = 1] - \Pr[D'(r) = 1]\big\rvert = \frac1{p(n)}\big\lvert\Pr[D(H^0) = 1] - \Pr[D(H^p) = 1]\big\rvert = \frac{\varepsilon(n)}{p(n)}$$

which is non-negligible: a contradiction.

∎

$H^i$: levels $0..i$ have independent uniform labels and lower levels are computed by $G$. $H^0$ is GGM and $H^n$ is a random function, so some neighbouring pair is distinguished with advantage at least $\varepsilon/n$.

The full level $i+1$ is exponential, so the reduction $D'$ fills the tree lazily. It receives $t(n)$ samples (one per possible query), each either $G(s)$ for fresh seeds or uniform $2n$-bit strings. Picking a random $i$, it labels the children of each newly reached level-$i$ node with the next sample, and answers repeated paths consistently. Pseudorandom samples give $H^i$; uniform samples give $H^{i+1}$. Many samples of $G$ are jointly pseudorandom (multi-sample theorem below), contradicting PRG security.

∎

$\mathcal A'$: choose random $m_0, m_1$ of length $2n/5$, receive $c = \mathrm{Enc}_k(m_b)$, run the inverter on $(c,m_0)$. If it returns $(k',m_0,r')$ with $\mathrm{Enc}_{k'}(m_0;r') = c$, output 0; else guess at random.

• $b = 0$: the inverter succeeds with probability at least $\varepsilon$, so $\Pr[\text{win}]\ge\frac12 + \frac\varepsilon2$.
• $b = 1$: success requires some key $k'$ with $\mathrm{Dec}_{k'}(c) = m_0$. By a union bound over $2^{n/5}$ keys and the independent uniform $m_0$ of $2n/5$ bits, this has probability at most $2^{n/5}/2^{2n/5} = 2^{-n/5}$. So $\Pr[\text{win}]\ge\frac12 - \frac12 2^{-n/5}$.

Overall $\frac12 + \frac\varepsilon4 - \frac14 2^{-n/5}$, a non-negligible advantage. The bound needs plaintext longer than key; it fails for one-time-pad-like schemes.

∎

$H^i = (X^{(1)},\ldots,X^{(i)},Y^{(i+1)},\ldots,Y^{(p)})$, with $H^0 = \bar Y$ and $H^p = \bar X$. $D'$, given one sample $\alpha$, picks a random $i$, samples $i$ copies of $X$ and $p - i - 1$ of $Y$ itself (this is where efficient samplability is needed), and places $\alpha$ at position $i + 1$. If $\alpha\sim X$ it gets $H^{i+1}$; if $\alpha\sim Y$, $H^i$. Telescoping gives advantage $\varepsilon/p$. Example: $(G(s_1),G(s_2))$ is a pseudorandom $2\ell$-bit string, as used in the GGM proof.

∎