# The Blum-Micali 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 random-looking bits.

The Blum-Micali 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 [Blum-Micali '81]: If $$B$$ is $$(t,\epsilon)$$-hardcore then $$G_{BM}$$ is a $$(t-m 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 $$(t-m TIME(f), m \epsilon)$$-PRNG. Then there exists a $$(t-m TIME(f))$$ algorithm $$A$$, and $$0 \le i \lt m$$ such that

$Pr[A(G_{BM}^R(S)|_{1...i}) = G_{BM}^R(S)|_{i+1}] \ge 1/2 + \epsilon$

We shall build an algorithm $$A'$$ that predicts $$B(x)$$ given $$f(x)$$.

Let $$S \in \{0,1\}^n$$ and define $$y = f^{m-i}(S)$$. Then

$\array { G^R_{BM}(S)|_{1...i} &=& [B(f^m(S)), B(f^{m-1}(S)),...,B(f^{m-i+1}(S))] \\ &=& [B(f^i(y)),...,B(f(y))] }$

Algorithm $$A'$$ acts as follows. Given $$z = f(y)$$,

1. Compute $$T(z) = [B(f^{i-1}(z)),...,B(z)]$$

2. Output $$A(T(z))$$.

Note that $$TIME(A')$$ = $$t$$. Then we wish to show that

$Pr[A'(f(y)) = B(y) | y \leftarrow \{0,1\}^n ] \ge 1/2 + \epsilon$

This follows since $$f$$ is a permutation and hence the distribution $$\{T_z|y\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,...,p-1\}\rightarrow\{1,...,p-1\}$$, $$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.

• Blum-Blum-Shub (BBS): $$N=pq$$ 1024-bit, $$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.

1. $$S\leftarrow QR_N$$

2. Output $$LSB(S)$$

3. $$S\leftarrow S^2 \pmod N$$

4. 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 1024-bit 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_k|r_1...r_k\leftarrow \{0,1\}^k$$.

The Blum-Micali Theorem remains true for simultaneously secure bits.

Best result for Dlog [Shamir-Schrift]: $$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.

Ben Lynn blynn@cs.stanford.edu 💡