Lower Bounds on Black-Box Constructions of Pseudorandom Functions

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 $\omega(\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 constr