ECCC-Report TR21-125https://eccc.weizmann.ac.il/report/2021/125Comments and Revisions published for TR21-125en-usSun, 12 Jun 2022 18:27:44 +0300
Revision 1
| The Exact Complexity of Pseudorandom Functions and the Black-Box Natural Proof Barrier for Bootstrapping Results in Computational Complexity |
Zhiyuan Fan,
Jiatu Li,
Tianqi Yang
https://eccc.weizmann.ac.il/report/2021/125#revision1Investigating 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.Sun, 12 Jun 2022 18:27:44 +0300https://eccc.weizmann.ac.il/report/2021/125#revision1
Paper TR21-125
| The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs |
Zhiyuan Fan,
Jiatu Li,
Tianqi Yang
https://eccc.weizmann.ac.il/report/2021/125How 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).Sun, 29 Aug 2021 06:10:52 +0300https://eccc.weizmann.ac.il/report/2021/125