# Constructing a PRF from PRG, with more parallelism

The famous result of Goldreich, Goldwasser, and Micali (GGM) constructs a PRF $$F$$ from a PRG $$G$$:

F(k,x):
v := k
for i = 1 to length(x):
if x[i] == 0 then v := left  half of G(v)
if x[i] == 1 then v := right half of G(v)
return v


($$G$$ is a PRG with outputs twice as long as inputs)

This PRF calls the PRG repeatedly, and these calls are all inherently sequential. Is there any known work on constructing a PRF from a PRG, which considers the parallelism of the PRG calls? Maybe a less sequential construction, or (more likely) an impossibility result that GGM is optimal in some way. I have to assume that this would be a natural question to study, but I am having trouble identifying any sources.

• I don’t know of anything from PRGs generically (except for using a PRG with larger expansion to get a wider, shallower “tree”), but works of Naor and Reingold (plus Rosen) gave PRFs with good parallelism from generic “synthesizers,” and even better parallelism from specific assumptions like DDH and factoring. Banerjee-Peikert-Rosen initiated analogous constructions from lattice problems. Commented Jul 26, 2022 at 21:21

## 1 Answer

The GGM construction uses $$\Theta(n)$$ depth of black-box calls to the PRG. There is a somewhat interesting limit to how much this might be improved: there is no black-box way of creating a PRF from a PRG that uses $$o(log(n))$$ depth, assuming the existence of a Pseudorandom Generator with Linear Stretch in NC0. Here, $$n$$ is the length of the PRF input $$x$$.

Proof: If such a black-box technique exists, instantiate it with a constant-depth PRG. The circuit depth will still be $$o(log(n))$$. Because each gate takes at two inputs, each output depends on at most $$2^{o(log(n))} < n$$ input bits, so each output bit much be independent of some of the input bits. Then this gives a simple distinguisher: pick an output bit, and an input bit that it does not dependent on. Query twice, where the only change is this input bit, and output $$1$$ iff the output bit did not change. For a random function it will output $$1$$ with probability $$1/2$$, but for this purported PRF the distinguisher will always output $$1$$.

• GGM uses $n$ calls, not $\log n$, to the underlying (length-doubling) PRG, where $n$ is the PRF input length. Your argument rules out using $o(\log n)$ calls, but doesn’t rule out improving GGM to use, say, $\sqrt{n}$ calls, or some other sub-linear, super-logarithmic number. Commented Jul 27, 2022 at 11:04
• @ChrisPeikert Oops, thanks for pointing that out! Commented Jul 27, 2022 at 23:41