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 💡