The BlumMicali Generator
Consider this simple idea for constructing a PRNG: seed the state with some key and pick some encryption algorithm such as DES. Then each iteration, encrypt the current state and output a few bits of it. Intuitively, this seems like it should produce randomlooking bits.
The BlumMicali scheme mimics this process, but on a firm theoretical foundation, by using hardcore bits.
Let \(f:\{0,1\}^n\rightarrow\{0,1\}^n\) be a permutation and \(B:\{0,1\}^n\rightarrow\{0,1\}\) be a \((t,\epsilon)\)hardcore bit of \(f\). Define \(G_{BM}:\{0,1\}^n\rightarrow\{0,1\}^m\) as follows:
Pick random seed \(S\in\{0,1\}^n\). For \(i=1\) to \(m\):

Output \(h_i = B(S)\)

\(S\leftarrow f(S)\)
Theorem [BlumMicali '81]: If \(B\) is \((t,\epsilon)\)hardcore then \(G_{BM}\) is a \((tm TIME(f), \epsilon m)\)PRNG.
Proof: First we devise notation to record the reverse of a bit string. Define \(G^R_{BM}(S) = [G_{BM}(S)]^R\), that is, if \(G_{BM}(S) = b_1 ... b_m\), then \(G^R_{BM}(S) = b_m ... b_1\).
Then note that if \(G_{BM}^R\) is a \((t,\epsilon)\)PRNG, then \(G_{BM}\) is also a \((t,\epsilon)\)PRNG.
Now suppose \(G_{BM}^R\) is not a \((tm TIME(f), m \epsilon)\)PRNG. Then there exists a \((tm TIME(f))\) algorithm \(A\), and \(0 \le i \lt m\) such that
We shall build an algorithm \(A'\) that predicts \(B(x)\) given \(f(x)\).
Let \(S \in \{0,1\}^n\) and define \(y = f^{mi}(S)\). Then
Algorithm \(A'\) acts as follows. Given \(z = f(y)\),

Compute \(T(z) = [B(f^{i1}(z)),...,B(z)]\)

Output \(A(T(z))\).
Note that \(TIME(A')\) = \(t\). Then we wish to show that
This follows since \(f\) is a permutation and hence the distribution \(\{T_zy\leftarrow\{0,1\}^n,z=f(y)\}\) is identical to the distribution \(\{G^R_{BM}(S)_{1...i}S\leftarrow\{0,1\}^n\}\).
This is a contradiction because \(B\) is \((t,\epsilon)\)hardcore for \(f\).
Examples of BM generators

Dlog generator: \(p = 1024\)bit prime, \(g\in\mathbb{Z}_p^*\) a generator. Let \(f:\{1,...,p1\}\rightarrow\{1,...,p1\}\), \(f(x)=g^x \bmod p\). We know \(MSB(x) = \{0 \text{if} x \lt p/2, 1 \text{if} x \gt p/2\) is a \((t,\epsilon)\)hardcore bit of \(f\) if no \(tn^3/\epsilon\)time discrete log algorithm exists. Thus we have a PRNG assuming Dlog is hard.

BlumBlumShub (BBS): \(N=pq\) 1024bit, \(p=q=3 \bmod 4\). Let \(QR_N = \{x\in\mathbb{Z}_N^*x \text{is QR}\}\). Then \(f(x) = x^2 \bmod N\) is a permutation of \(QR_N\). LSB(x) is \((t,\epsilon)\)hardcore for \(f\) assuming no \((tn^2/\epsilon)\) factoring algorithm exists.

\(S\leftarrow QR_N\)

Output \(LSB(S)\)

\(S\leftarrow S^2 \pmod N\)

Goto step 1
[BBS not \((t,\epsilon)\)hardcore implies LSB is not \((t,\epsilon/m)\)hardcore (where \(m\) is the number of output bits), which implies there exists a \(t(n^m/\epsilon)^2\)time factoring algorithm (where \(n = lg N\)).]
Example: suppose no \(2^{100}\)time factoring algorithm exists for 1024bit numbers, and that \(m = 2^{20}\). Then we get that BBS is secure for \(t/\epsilon^2 = 2^{40}\), e.g. BBS is a \((2^{20}, 2^{10})\)PRNG, which is not secure.

Faster BM
We can output one bit per application of \(f\). Can we output more?
For Dlog it turns out that for \(i=1,...,n/2\) the msb_i(x) is a hardcore bit. But this is not enough. We need a notion of simultaneous security.
Definition: Let \(f:\{0,1\}^n\rightarrow\{0,1\}\). Then bits \(B_1,...,B_k:\{0,1\}^n\rightarrow\{0,1\}\) are \((t,\epsilon)\)simultaneously secure if \(\{f(x), B_1(x),...,B_k(x)x\in\{0,1\}\}\) is \((t,\epsilon)\)indistinguishable from \(\{f(x),r_1,...,r_kr_1...r_k\leftarrow \{0,1\}^k\).
The BlumMicali Theorem remains true for simultaneously secure bits.
Best result for Dlog [ShamirSchrift]: \(N=pq, f(x)=g^x \bmod N\). Then the bits in the most significant half of \(x\) are \((t,\epsilon)\)simultaneously secure for \(f\) assuming no \(O(t(n/\epsilon)^3)\)time factoring algorithms exist.