]> 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{0,1 } n be a permutation and B:{0,1 } n{0,1 } be a (t,ε)-hardcore bit of f. Define G BM:{0,1 } n{0,1 } m as follows:

Pick random seed S{0,1 } n. For i=1 to m 1. Output h i=B(S) 2. Sf(S)

Theorem [Blum-Micali '81]: If B is (t,ε)-hardcore then G BM is a (tmTIME(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 (tmTIME(f),mε)-PRNG. Then there exists a (tmTIME(f)) algorithm A, and 0 i<m such that

Pr[A(G BM R(S) 1 ...i)=G BM R(S) i+1 ]1 /2 +ε

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

Let S{0,1 } n and define y=f mi(S). Then

G BM R(S) 1 ...i = [B(f m(S)),B(f m1 (S)),...,B(f mi+1 (S))] = [B(f i(y)),...,B(f(y))]

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

  1. Compute T(z)=[B(f i1 (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{0,1 } n]1 /2 +ε

This follows since f is a permutation and hence the distribution {T zy{0,1 } n,z=f(y)} is identical to the distribution {G BM R(S) 1 ...iS{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 p * a generator. Let f:{1 ,...,p1 }{1 ,...,p1 }, f(x)=g xmodp. We know MSB(x)={0 ifx<p/2 ,1 ifx>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 mod4 . Let QR N={x N *xis QR}. Then f(x)=x 2 modN is a permutation of QR N. LSB(x) is (t,ε)-hardcore for f assuming no (tn 2 /ε) factoring algorithm exists.

    1. SQR N

    2. Output LSB(S)

    3. SS 2 (modN)

    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=lgN).]

    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{0,1 }. Then bits B 1 ,...,B k:{0,1 } n{0,1 } are (t,ε)-simultaneously secure if {f(x),B 1 (x),...,B k(x)x{0,1 }} is (t,ε)-indistinguishable from {f(x),r 1 ,...,r kr 1 ...r k{0,1 } k.

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

Best result for Dlog [Shamir-Schrift]: N=pq,f(x)=g xmodN. 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.