4
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 26, 2022 at 21:21

1 Answer 1

2
$\begingroup$

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$.

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Jul 27, 2022 at 11:04
  • $\begingroup$ @ChrisPeikert Oops, thanks for pointing that out! $\endgroup$
    – qbt937
    Commented Jul 27, 2022 at 23:41

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.