Goldreich-Goldwasser-Micali Construction

Question

The Goldreich-Goldwasser-Micali construction allows to build a (cryptographically secure) pseudo-random function from of a (cryptographically secure) pseudo-random generator.

More formally, let $G: \{0, 1\}^s \rightarrow \{0, 1\}^{2s}$ be a length-doubling PRNG. Given a seed $s$, $G(s)$ returns a $2s$-bit string $G(s) = G_1(s)||G_0(s)$, where $||$ denotes the concatenation. Then, the GGM construction works as follows: given a key $k\in\{0, 1\}^s$ and an input $x=x_{n-1}||\dots||x_{0}\in\{0, 1\}^n$, the output $y \in \{0, 1\}^s$ is computed as $y = F_k(x) = G_{x_{n-1}}(G_{x_{n-2}}(\dots(G_{x_0}(k))\dots))$.

In terms of efficiency, the GGM construction needs $n$ calls to the PRNG for an $n$-bit input. Is there a more efficient, but still provably secure construction, i.e., a construction making less calls to the PRNG? Any pointer on a paper is welcome!

Answer 1

Levin showed that combining PRG with a universal hash function, one can reduce the number of calls. Roughly speaking, we shorten a message with a universal hash function before applying the GGM construction. That is, $y = F_{k,k'}(x) = \mathrm{GGM}_G(k,h(k',x))$, where $h$ is a universal hash function.

At TCC 2012, Jain, Pietrzak, and Tentes gave another technique to reduce the number of calls with preserving hardness by using t-wise independent hash functions. See their paper for details.

Leonid A. Levin. One-way functions and pseudorandom generators. Combinatorica, 7(4):357-363, 1987. Levin87

Abhishek Jain, Krzysztof Pietrzak, Aris Tentes: Hardness Preserving Constructions of Pseudorandom Functions. TCC 2012: 369-382. JPT12