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 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.

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

    1. $S\leftarrow QR_N$

    2. Output $LSB(S)$

    3. $S\leftarrow S^2 (mod 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.

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_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 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.