Lower Bounds on Black-Box Constructions of Pseudorandom Functions

Bar Alon, Itai Dinur, Muthuramakrishnan Venkitasubramaniam

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 co…