Cryptology ePrint Archive: Report 2021/1079

The Exact Complexity of Pseudorandom Functions and Tight Barriers to Lower Bound Proofs

Zhiyuan Fan and Jiatu Li and 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).

Category / Keywords: foundations / circuit complexity, natural proofs, pseudorandom functions, random restrictions, threshold circuit

Date: received 22 Aug 2021, last revised 22 Aug 2021

Contact author: yangtq19 at mails tsinghua edu cn, lijt19 at mails tsinghua edu cn, fan-zy19 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20210823:063716 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]