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

• DOI: 10.1145/3519935.3520010
• Publication Date: 2022-06-10T15:29:32Z
• Authors: Zhiyuan Fan; Jiatu Li; Tianqi Yang
• Keywords: Pseudorandom function family; Bootstrapping (finance); Circuit complexity; Black box; Pseudorandom generator theorem

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 exact complexity PRFs by proving tight upper lower bounds various circuit models.