A classical challenge in complexity theory and cryptography is to simulate interactive proof systems by non-interactive proof systems. In this work we leverage approaches from recent works in derandomization to address this challenge, focusing on non-interactive simulations that are sound against uniform adversarial algorithms.
Our results concern fundamental questions in complexity theory, such as the $\mathcal{NP}$ vs $\mathcal{PSPACE}$ question, and also in cryptography, such as the question of constructing non-interactive zero-knowledge arguments for $\mathcal{NP}$ from unstructured assumptions. Relying on strong complexity-theoretic hardness assumptions (that will be described below):
1. *Complexity theory.* We prove that $\mathcal{PSPACE}$ is contained in the ``computationally sound'' version of $\mathcal{NP}$. Specifically, for every $L\in\mathcal{PSPACE}$, membership in $L$ can be verified by an $\mathcal{NP}$-type (deterministic, polynomial-time) verifier $V$ with the following guarantee: The verifier accepts every $x\in L$ when given a proof $\pi$ from an honest prover that runs in fixed exponential time $T_P$; and every uniform adversary running in probabilistic time $\mathrm{poly}(T_P)$ cannot find $x\notin L$ and $\pi$ such that $V(x,\pi)=1$, except with negligible probability in $T_P$. As a corollary in the area of bounded arithmetic, under the same assumptions, we deduce that $\mathcal{NP}\ne\mathcal{PSPACE}$ is not provable in the theory ${APC}_1$. This is a strong theory, which captures many of the major results in complexity.
2. *Cryptography.* We construct new cryptographic protocols, including succinct non-interactive arguments (${SNARG}$s) for $\mathcal{NC}$ in the plain model, as well as non-interactive zero-knowledge and witness indistinguishable (${NIZK}$ and ${NIWI}$) proof systems for $\mathcal{NP}$, all with computational soundness against uniform adversaries. The ${SNARG}$ relies solely on the aforementioned complexity-theoretic assumption, whereas the ${NIZK}$ and ${NIWI}$ require also a sub-exponentially secure one-way function (which should be injective in the case of the ${NIWI}$). These are the first constructions of the above protocols that do not rely on highly structured cryptographic primitives.
Roughly speaking, following Chen and Tell (FOCS 2021, STOC 2023), the complexity-theoretic hardness assumptions throughout our paper assert the existence of functions $f \colon \{0,1\}^n \to \{0,1\}^k$ that are computable in polynomial time and hard for bounded-space machines (say, linear space) in a strong average-case sense: No efficient algorithm can find an input $x$ on which the bounded-space machine computes $f$, except with negligible probability.
