]> Cryptography - The Goldreich-Goldwasser-Micali Construction

This is a method of using a PRNG to construct a PRF [GGM'84].

Let G:{0,1 } s{0,1 } 2 s be a PRNG.

Define G 0 ,G 1 to be the left and right halves of G, so that G(X)=G 0 (X)G 1 (X).

For any K{0,1 } s, define F K:{0,1 } n{0,1 } s by

F K(x 1 ...x n)=G x n(G x n1 (...(G x 2 (G x 1 (K))...))

Theorem: If G is a (t,ε)-PRNG then F is a (tcn,εqn,q)-PRF for some constant c.

Proof: We use a hybrid argument. For i=0 ,...,n define

F h i i(x 1 ,...,x n)=G x n(G x n1 (...(G xi+1 (h i(x i...x 1 )))...))

where h i is a function h i:{0,1 } i{0,1 } s. Observe h 0 is a constant in {0,1 } s.

Also define the distributions

D i={F h i ih i{h:{0,1 } i{0,1 } s}}

Observe D 0 ={F K GGM} K{0,1 } s and D n={F} F