Muthuramakrishnan Venkitasubramaniam

Lower Bounds on Black-Box Constructions of Pseudorandom Functions

This work considers 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.