Welcome to the resource topic for 2021/1079
Title:
The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs
Authors: Zhiyuan Fan, Jiatu Li, Tianqi Yang
Abstract: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).
ePrint: https://eprint.iacr.org/2021/1079
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .