Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|improve this question
up vote 4 down vote accepted

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

share|improve this answer
Many thanks for the quick and useful answer! – cryptopathe Jun 18 '12 at 18:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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