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\):
-
Output \(h_i = B(S)\)
-
\(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
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
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
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.
-
\(S\leftarrow QR_N\)
-
Output \(LSB(S)\)
-
\(S\leftarrow S^2 \pmod N\)
-
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.