Cryptography - 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} \to {0,1}^{n}$ be a permutation and $B : {0,1}^{n} \to {0,1}$ be a $(t, ε)$ -hardcore bit of $f$ . Define $G_{BM} : {0,1}^{n} \to {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, ε)$ -hardcore then $G_{BM}$ is a $(t - m TIME (f), ε m)$ -PRNG.

Proof: First we devise notation to record the reverse of a bit string. Define $G_{BM}^{R} (S) = [G_{BM} (S)]^{R}$ , that is, if $G_{BM} (S) = b_{1} . . . b_{m}$ , then $G_{BM}^{R} (S) = b_{m} . . . b_{1}$ .

Then note that if $G_{BM}^{R}$ is a $(t, ε)$ -PRNG, then $G_{BM}$ is also a $(t, ε)$ -PRNG.

Now suppose $G_{BM}^{R}$ is not a $(t - m TIME (f), m ε)$ -PRNG. Then there exists a $(t - m TIME (f))$ algorithm $A$ , and $0 \leq i < m$ such that

\Pr [A (G_{BM}^{R} (S) ∣_{1 . . . i}) = G_{BM}^{R} (S) ∣_{i + 1}] \geq 1 / 2 + ε

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

\begin{matrix} G_{BM}^{R} (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))] \end{matrix}

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

Compute $T (z) = [B (f^{i - 1} (z)), . . ., B (z)]$
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}] \geq 1 / 2 + ε

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_{BM}^{R} (S) ∣_{1 . . . i} ∣ S \leftarrow {0,1}^{n}}$ .

This is a contradiction because $B$ is $(t, ε)$ -hardcore for $f$ .

Examples of BM generators

Dlog generator: $p = 1024$ -bit prime, $g \in ℤ_{p}^{*}$ a generator. Let $f : {1, . . ., p - 1} \to {1, . . ., p - 1}$ , $f (x) = g^{x} \mod p$ . We know $MSB (x) = {0 if x < p / 2, 1 if x > p / 2$ is a $(t, ε)$ -hardcore bit of $f$ if no ${tn}^{3} / ε$ -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 ℤ_{N}^{*} ∣ x is QR}$ . Then $f (x) = x^{2} \mod N$ is a permutation of ${QR}_{N}$ . LSB(x) is $(t, ε)$ -hardcore for $f$ assuming no $({tn}^{2} / ε)$ 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, ε)$ -hardcore implies LSB is not $(t, ε / m)$ -hardcore (where $m$ is the number of output bits), which implies there exists a $t (n^{m} / ε)^{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} \to {0,1}$ . Then bits $B_{1}, . . ., B_{k} : {0,1}^{n} \to {0,1}$ are $(t, ε)$ -simultaneously secure if ${f (x), B_{1} (x), . . ., B_{k} (x) ∣ x \in {0,1}}$ is $(t, ε)$ -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, ε)$ -simultaneously secure for $f$ assuming no $O (t (n / ε)^{3})$ -time factoring algorithms exist.