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!

  • 1
    $\begingroup$ Any leads from where I could learn more about the GGM tree constrution? $\endgroup$
    – Het
    Commented Nov 29, 2023 at 8:16

1 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.