
$S\leftarrow QR_N$

Output $LSB(S)$

$S\leftarrow S^2 (mod N)$

Goto step 1
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$ 1. Output $h_i = B(S)$ 2. $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 mod 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 mod 4$. Let $QR_N = \{x\in\mathbb{Z}_N^*x \text{is QR}\}$. Then $f(x) = x^2 mod N$ is a permutation of $QR_N$. LSB(x) is $(t,\epsilon)$hardcore for $f$ assuming no $(tn^2/\epsilon)$ factoring algorithm exists.
[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.
Speeding up 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 mod 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.