In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by $(2n + o(n))$-gate circuits of fan-in $2$ over the $B_2$ basis. Applying this family, they established the existence of pseudorandom functions computable by circuits of the same complexity, under the standard assumption that OWFs exist. However, a major disadvantage of the hash family construction by Fan, Li, and Yang (STOC 2022) is that it requires a seed length of $\text{poly}(n)$, which limits its potential applications.
We address this issue by giving an improved construction of almost-universal hash functions with seed length $\text{polylog}(n)$, such that each function in the family is computable with $\text{POLYLOGTIME}$-uniform $(2n + o(n))$-gate circuits. Our new construction has the following applications in both complexity theory and cryptography.
* $\textbf{(Hardness magnification)}$. Let $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ be any function such that $\alpha(n) \leq \log n / \log \log n$. We show that if there is an $n^{\alpha(n)}$-sparse $\textbf{NP}$ language that does not have probabilistic circuits of $2n + O(n/\log\log n)$ gates, then we have (1) $\textbf{NTIME}[2^n] \not\subseteq \textbf{SIZE} \left[2^{n^{1/5}}\right]$ and (2) $\textbf{NP} \not\subseteq \textbf{SIZE}[n^k]$ for every constant $k$. Complementing this magnification phenomenon, we present an $O(n)$-sparse language in $\P$ which requires probabilistic circuits of size at least $2n - 2$. This is the first result in hardness magnification showing that even a sub-linear additive improvement on known circuit size lower bounds would imply $\textbf{NEXP} \not\subset \textbf{P}_{/\text{poly}}$.
Following Chen, Jin, and Williams (STOC 2020), we also establish a sharp threshold for explicit obstructions: we give an explict obstruction against $(2n-2)$-size circuits, and prove that a sub-linear additive improvement on the circuit size would imply (1) $\textbf{DTIME}[2^n] \not\subseteq \textbf{SIZE} \left[2^{n^{1/5}}\right]$ and (2) $\textbf{P} \not\subseteq \textbf{SIZE}[n^k]$ for every constant $k$.
* $\textbf{(Extremely efficient construction of pseudorandom functions)}$. Assuming that one of integer factoring, decisional Diffie-Hellman, or ring learning-with-errors is sub-exponentially hard, we show the existence of pseudorandom functions computable by $\text{POLYLOGTIME}$-uniform $\textbf{AC}^0[2]$ circuits with $2n + o(n)$ wires, with key length $\text{polylog}(n)$. This improves the key length and uniformity of previous PRF constructions of Fan, Li, and Yang (STOC 2022). We also show that PRFs computable by $\text{POLYLOGTIME}$-uniform $B_2$ circuits of $2n + o(n)$ gates follows from the existence of sub-exponentially secure one-way functions.

add some references

In a recent work, Fan, Li, and Yang (STOC 2022) constructed a family of almost-universal hash functions such that each function in the family is computable by $(2n + o(n))$-gate circuits of fan-in $2$ over the $B_2$ basis. Applying this family, they established the existence of pseudorandom functions computable by circuits of the same complexity, under the standard assumption that OWFs exist. However, a major disadvantage of the hash family construction by Fan, Li, and Yang (STOC 2022) is that it requires a seed length of $\text{poly}(n)$, which limits its potential applications.

We address this issue by giving an improved construction of almost-universal hash functions with seed length $\text{polylog}(n)$, such that each function in the family is computable with $\text{POLYLOGTIME}$-uniform $(2n + o(n))$-gate circuits. Our new construction has the following applications in both complexity theory and cryptography.

* ($\textbf{Hardness magnification}$). Let $\alpha : \mathbb{N} \rightarrow \mathbb{N}$ be any function such that $\alpha(n) \leq \log n / \log \log n$. We show that if there is an $n^{\alpha(n)}$-sparse $\textbf{NP}$ language that does not have probabilistic circuits of $2n + O(n/\log\log n)$ gates, then we have (1) $\textbf{NTIME}[2^n] \not\subseteq \textbf{SIZE} \left[2^{n^{1/5}}\right]$ and (2) $\textbf{NP} \not\subseteq \textbf{SIZE}[n^k]$ for every constant $k$. Complementing this magnification phenomenon, we present an $O(n)$-sparse language in $\textbf{P}$ which requires probabilistic circuits of size at least $2n - 2$. This is the first result in hardness magnification showing that even a \emph{sub-linear additive} improvement on known circuit size lower bounds would imply $\textbf{NEXP} \not\subseteq \textbf{P}_{/\text{poly}}$.

Following Chen, Jin, and Williams (STOC 2020), we also establish a sharp threshold for \textbf{explicit obstructions}: we give an explict obstruction against $(2n-2)$-size circuits, and prove that a sub-linear additive improvement on the circuit size would imply (1) $\textbf{DTIME}[2^n] \not\subseteq \textbf{SIZE} \left[2^{n^{1/5}}\right]$ and (2) $\textbf{P} \not\subseteq \textbf{SIZE}[n^k]$ for every constant $k$.

* ($\textbf{Extremely efficient construction of pseudorandom functions}$). Assuming that one of integer factoring, decisional Diffie-Hellman, or ring learning-with-errors is sub-exponentially hard, we show the existence of pseudorandom functions computable by $\text{POLYLOGTIME}$-uniform $\textbf{AC}^0[2]$ circuits with $2n + o(n)$ wires, with key length $\text{polylog}(n)$. We also show that PRFs computable by $\text{POLYLOGTIME}$-uniform $B_2$ circuits of $2n + o(n)$ gates follows from the existence of sub-exponentially secure one-way functions.