Paper 2026/006

SNARGs for NP and Non-Signaling PCPs, Revisited

Abstract

We revisit the question of whether it is possible to build succinct non-interactive arguments ($\mathsf{SNARG}$s) for all of $\mathsf{NP}$ under standard assumptions using non-signaling probabilistically checkable proofs [Kalai-Raz-Rothblum, STOC' 14]. In particular, we observe that using exponential-length PCPs appears to circumvent all of the existing barriers. For our main result, we give a candidate non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ and prove its soundness under: - the learning with errors assumption (or other standard assumptions such as bilinear maps), and - a mathematical conjecture about multivariate polynomials over the reals. In more detail, our conjecture is an upper bound on the minimum total coefficient size of Nullstellensatz proofs (Potechin-Zhang, ICALP 2024) of membership in a concrete polynomial ideal. We emphasize that this is not a cryptographic assumption or any form of computational hardness assumption. Of particular interest is the fact that our security analysis makes non-black-box use of the $\mathsf{SNARG}$ adversary, circumventing the black-box barrier of Gentry and Wichs (STOC '11). This gives a blueprint for constructing $\mathsf{SNARG}$s for $\mathsf{NP}$ that is not subject to the Gentry-Wichs barrier.