1 Block machines, hashing, and the target generator
Fix integers \(w,n,k \ge 0\). A randomized program that receives its random bits in \(k\) blocks of \(n\) bits and uses at most \(w\) bits of information between two consecutive blocks is represented by a finite state machine \(Q\) with \(2^w\) states over the alphabet \(\{ 0,1\} ^n\). There is a fixed start state and an arbitrary set of accepting states. For every state \(v\) and every block \(a \in \{ 0,1\} ^n\), exactly one outgoing edge from \(v\) is labelled by a set containing \(a\); following that edge is the transition caused by feeding block \(a\) to the original program.
A map \(G:\{ 0,1\} ^m \to (\{ 0,1\} ^n)^k\) is a pseudorandom generator for \(\operatorname {Space}(w)\) and block size \(n\) with parameter \(\varepsilon \) if for every finite state machine \(Q\) of size \(2^w\) over alphabet \(\{ 0,1\} ^n\),
Let \(\mathcal{H}\) be a finite set of functions \(h:\{ 0,1\} ^n \to \{ 0,1\} ^m\). The family \(\mathcal{H}\) is universal if for all distinct \(x_1,x_2 \in \{ 0,1\} ^n\) and all \(y_1,y_2 \in \{ 0,1\} ^m\),
Thus a uniformly selected member of \(\mathcal{H}\) sends two distinct inputs to two prescribed outputs with exactly the probability obtained from two independent uniform \(m\)-bit strings.
For \(x \in \{ 0,1\} ^n\), let \(a \in \{ 0,1\} ^{m+n-1}\) and \(b \in \{ 0,1\} ^m\). Define \((a*x)_j=\sum _{i=1}^{n} a_{i+j-1}x_i \pmod2\) for \(1 \le j \le m\), and set \(h_{a,b}(x)=a*x+b\), where \(+\) is bitwise exclusive-or. The family \(\mathcal{H}=\{ h_{a,b}:a \in \{ 0,1\} ^{m+n-1},\, b \in \{ 0,1\} ^m\} \) has descriptions of length \(O(n+m)\) and can be evaluated by one convolution plus one xor.
The convolution family of Construction 4 is a universal family of functions from \(\{ 0,1\} ^n\) to \(\{ 0,1\} ^m\).
Fix distinct \(x_1,x_2\) and desired outputs \(y_1,y_2\). Since \(x_1 \ne x_2\), choose an index \(r\) with \((x_1)_r \ne (x_2)_r\). For any fixed \(a\), the condition \(h_{a,b}(x_1)=y_1\) determines the unique value \(b=y_1+a*x_1\). With this value of \(b\), the second condition becomes \(a*(x_1+x_2)=y_1+y_2\) over \(\mathbb F_2\). The vector \(x_1+x_2\) is nonzero. For each output coordinate \(j\), the equation \(\sum _i a_{i+j-1}(x_1+x_2)_i=(y_1+y_2)_j\) contains the variable \(a_{r+j-1}\) with coefficient \(1\) and no later equation contains an incompatible copy of that same solved variable in the triangular ordering obtained by eliminating coordinates one at a time. Hence exactly a \(2^{-m}\) fraction of choices of \(a\) satisfy the \(m\) equations. Multiplying by the \(2^{-m}\) probability of the determined value of \(b\) gives \(2^{-2m}\). This is precisely Definition 3.