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. * PRFs can be constructed in 2 n + o ( n ) size general circuits assuming the existence of polynomial-size PRFs, simplifying and improving the O ( n ) upper bound by Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC 2008). Moreover, if PRFs exist in NC 1 , we can further guarantee the depth of our construction to be (1+є) log n . We show that our construction is almost optimal by giving an unconditional 2 n − O (1) lower bound. * PRFs can be constructed in AC 0 [2] circuits of o ( n ) gates and 2 n + o ( n ) wires assuming the existence of polynomial-size AC 0 [2] PRFs. We show the optimality of our construction with a 2 n +Ω(√ n ) wire complexity lower bound. * PRFs can be constructed with wire complexity n 1+ O (1.61 − d ) in depth- d TC 0 circuits assuming the existence of polynomial-size TC 0 PRFs. We also present an n 1+Ω( c − d ) wire complexity lower bound against depth- d TC 0 circuits for some c >1.61. As a byproduct, we prove unconditional tight upper and lower bounds for ”almost” universal hash functions that are of independent interest. Following the natural proof barrier of Razborov and Rudich (J. Comput. Syst. Sci. 1997), we observe that our exact complexity results are closely related to the ”bootstrapping phenomena” in circuit complexity (such as hardness magnification and quantified derandomization). We introduce the black-box natural proof barrier and show that a large range of techniques for bootstrapping results cannot be combined with ”black-box” lower bound proofs to obtain a breakthrough.

Authors

• Zhiyuan Fan
• Jiatu Li
• Tianqi Yang 0001

Keywords

• Boolean circuits
• circuit complexity
• natural proofs
• pseudorandom functions
• random restrictions
• threshold circuits