Paper 2024/1104

Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Amos Beimel, Ben-Gurion University of the Negev
Tal Malkin, Columbia University
Noam Mazor, Tel Aviv University

We address the black-box complexity of constructing pseudorandom functions (PRF) from pseudorandom generators (PRG). The celebrated GGM construction of Goldreich, Goldwasser, and Micali (Crypto 1984) provides such a construction, which (even when combined with Levin's domain-extension trick) has super-logarithmic depth. Despite many years and much effort, this remains essentially the best construction we have to date. On the negative side, one step is provided by the work of Miles and Viola (TCC 2011), which shows that a black-box construction which just calls the PRG once and outputs one of its output bits, cannot be a PRF. In this work, we make significant further progress: we rule out black-box constructions of PRF from PRG that follow certain structural constraints, but may call the PRG adaptively polynomially many times. In particular, we define ``tree constructions" which generalize the GGM structure: they apply the PRG $G$ along a tree path, but allow for different choices of functions to compute the children of a node on the tree and to compute the next node on the computation path down the tree. We prove that a tree construction of logarithmic depth cannot be a PRF (while GGM is a tree construction of super-logarithmic depth). We also show several other results and discuss the special case of one-call constructions. Our main results in fact rule out even weak PRF constructions with one output bit. We use the oracle separation methodology introduced by Gertner, Malkin, and Reingold (FOCS 2001), and show that for any candidate black-box construction $F^G$ from $G$, there exists an oracle relative to which $G$ is a PRG, but $F^G$ is not a PRF.

Available format(s)
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Contact author(s)
amos beimel @ gmail com
tal @ cs columbia edu
noammaz @ gmail com
2024-07-10: revised
2024-07-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Amos Beimel and Tal Malkin and Noam Mazor},
      title = {Structural Lower Bounds on Black-Box Constructions of Pseudorandom Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1104},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.