The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity

Investigating the computational resources we need for cryptography is an essential task of both theoretical and practical interests. This paper provides answers to this problem on pseudorandom functions (PRFs). We resolve the exact complexity of PRFs by proving tight upper and lower bounds for various circuit models.