Lower Bounds on Black-Box Constructions of Pseudorandom Functions
2026-08-14 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
The authors study how efficiently one can build pseudorandom functions (PRFs) using pseudorandom generators (PRGs) in a black-box way, meaning without knowing the inner workings of the PRG. They focus on constructions where the number of times the PRG is called is as small as possible. Building on past work, they prove it is impossible to have very few non-adaptive calls to the PRG—specifically fewer than about n divided by log n, where n is the input size. This applies even to simple PRFs with 1-bit outputs and random queries. They also show a lower bound when the construction can adaptively query the PRG for weak PRFs with long outputs.
Pseudorandom Function (PRF)Pseudorandom Generator (PRG)Black-box ConstructionNon-adaptive QueriesAdaptive QueriesGoldreich-Goldwasser-Micali (GGM) ConstructionLevin's Domain ExtensionWeak PRFOracle AccessLower Bounds in Cryptography
Authors
Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam
Abstract
In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When combined with Levin's domain extension technique, the GGM construction invokes the PRG $ω(\log n)$ times, where $n$ denotes the input length to the PRG. To this day, no black-box construction achieving fewer calls is known. Recently, Beimel, Malkin, and Mazor [CRYPTO 2024] showed that for a certain family of constructions, which they termed \emph{tree constructions}, the GGM construction is optimal. However, the basic challenge of whether a PRF can be built with just \emph{one invocation} of the PRG still remains open. In this work, we consider fully black-box constructions of PRFs from PRGs, where both the construction and the reduction are required to be black-box, and the number of interactions the reduction makes with the adversary is independent of the number of oracle calls the adversary makes to its underlying function within each interaction. Our main result shows that no such construction can have $o(n/\log n)$ and $o(\mathsf{in}/\log\mathsf{in})$ \emph{non-adaptive} calls to the PRG, where $\mathsf{in}$ is the input length of the PRF. This impossibility holds even for weak PRFs with one-bit output, where the adversary is restricted to making i.i.d. uniformly random queries. In addition, we prove a lower bound for weak PRFs with sufficiently long outputs that holds even when the construction is allowed to make adaptive queries to the PRG.