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 $2n + 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 $\mathsf{NC}^1$, we can further guarantee the depth of our construction to be $(1+\epsilon) \log n$. We show that our construction is almost optimal by giving an unconditional $2n-O(1)$ lower bound.
* PRFs can be constructed in $\mathsf{AC}^0[2]$ circuits of $o(n)$ gates and $2n+o(n)$ wires assuming the existence of polynomial-size $\mathsf{AC}^0[2]$ PRFs. We show the optimality of our construction with a $2n+\Omega(\sqrt n)$ wire complexity lower bound.
* PRFs can be constructed with wire complexity $n^{1+O(1.61^{-d})}$ in depth-$d$ $\mathsf{TC}^0$ circuits assuming the existence of polynomial-size $\mathsf{TC}^0$ PRFs. We also present an $n^{1+\Omega(c^{-d})}$ wire complexity lower bound against depth-$d$ $\mathsf{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.
- Add upper and lower bounds in AC0[2] circuits.
- Rewrite the section on the black-box natural proofs
- Rewrite and re-organize many sections of the paper to improve the readability and make the results more accessible.
* Swap Section 2 and Section 3. We find it helpful for the readers to have a brief understanding of the proof to understand the black-box natural proof.
* Rewrite the first two sections (“Introduction” and “Proof Overview”) to improve the readability
* Rewrite Section 3 (“A new barrier for bootstrapping results in circuit complexity”). We hope this can make the black-box natural proof clearer and show its connections with the bootstrapping results.
* Extract the upper bounds in low-depth circuits from the original Section 5 and form a new Section 6.
How much computational resource do we need for cryptography? This is an important question of both theoretical and practical interests. In this paper, we study the problem on pseudorandom functions (PRFs) in the context of circuit complexity. Perhaps surprisingly, we prove extremely tight upper and lower bounds in various circuit models.
* In general $B_2$ circuits, assuming the existence of PRFs, PRFs can be constructed in $2n + o(n)$ size, simplifying and improving the $O(n)$ bound by Ishai et al. (STOC 2008). We show that such construction is almost optimal by giving an unconditional $2n-O(1)$ lower bound.
* In logarithmic depth circuits, assuming the existence of $NC^1$ PRFs, PRFs can be constructed in $2n + o(n)$ size and $(1+\epsilon) \log n$ depth simultaneously.
* In constant depth linear threshold circuits, assuming the existence of $TC^0$ PRFs, PRFs can be constructed with wire complexity $n^{1+O(1.61^{-d})}$. We also give an $n^{1+\Omega(c^{-d})}$ wire complexity lower bound for some constant $c$.
The upper bounds are proved with generalized Levin's trick and novel constructions of "almost" universal hash functions; the lower bound for general circuits is proved via a tricky but elementary wire-counting argument; and the lower bound for $TC^0$ circuits is proved by extracting a "black-box" property of $TC^0$ circuits from the "white-box" restriction lemma of Chen, Santhanam, and Srinivasan (Theory Comput. 2018). As a byproduct, we prove unconditional tight upper and lower bounds for "almost" universal hashing, which we believe to have independent interests.
Following Natural Proofs by Razborov and Rudich (J. Comput. Syst. Sci. 1997), our results make progress in realizing the difficulty to improve known circuit lower bounds which recently becomes significant due to the discovery of several "bootstrapping results". In $TC^0$, this reveals the limitation of the current restriction-based methods; in particular, it brings new insights in understanding the strange phenomenon of "sharp threshold results" such as the one presented by Chen and Tell (STOC 2019).
