Paper 2026/2803

The GGM PRF Construction is Optimal

Abstract

We study the complexity of fully black-box constructions of pseudorandom functions (PRFs) from pseudorandom generators (PRGs). The seminal work of Goldreich, Goldwasser, and Micali (JACM 1986), combined with Levin’s domain-extension technique, yields PRFs that make a superlogarithmic number of adaptive calls to a length-doubling PRG. A long-standing open problem is whether fewer calls suffice for fully black-box constructions. Despite progress for restricted classes of constructions and reductions, previous results have not been able to rule out even a single-call construction in full generality. A related question asks how many calls are needed to amplify a PRG’s stretch from \(r\) bits to \(\rho>r\) bits. Our main result establishes the asymptotic optimality of the GGM construction with domain compression, both in the number of calls and in adaptivity, for length-doubling PRGs. More generally, for a PRG with seed length \(n\) and stretch \(r(n)\), we rule out fully black-box PRF constructions with \(d(n)\) adaptive rounds whenever \(d(n)\log(2+r(n)/n)=O(\log n)\), even allowing polynomially many calls per round. Our bounds hold for one-bit weak PRFs on domains of superpolynomial size. In particular, they exclude all polynomial-query nonadaptive constructions from PRGs of arbitrary polynomial stretch and require superlogarithmically many rounds when the underlying PRG doubles its input length. We further show impossibility results for fully black-box non-adaptive PRG stretch amplification. First, we show that a non-adaptive construction of a $\rho$-bit stretch PRG from an $r$-bit stretch PRG requires $\Omega(\tfrac{\rho}{r+\log n})$ calls. Second, we show that it is impossible to construct a length-doubling PRG from an $o(n)$-bit stretch PRG with non-adaptive calls. Our techniques combine and extend two prior lines of work. First, we develop a sensitivity framework that measures the effect of changing a uniformly chosen oracle entry and transfers this stability through black-box reductions, extending the sensitivity arguments of Bitansky et al. (CRYPTO 2017) and Bitansky and Degwekar (TCC 2019). Second, we extend the scoring mechanism of Alon et al. (CRYPTO 2026) and integrate it with our framework. Finally, we show that the sensitivity framework applies to constructions from one-way permutations. Specifically, we show another proof of Simon's impossibility of basing collision-resistant hash functions on one-way permutations. Our new proof can be viewed as an abstraction of the argument by Bitansky and Degwekar.