期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 B2 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 NC1 PRFs, PRFs can be constructed in 2n+o(n) size and (1+)logn depth simultaneously. * In constant depth linear threshold circuits, assuming the existence of TC0 PRFs, PRFs can be constructed with wire complexity n1+O(161−d). We also give an n1+(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 TC0 circuits is proved by extracting a "black-box" property of TC0 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 TC0, 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).
