1970-01-01

(2026-01) SNARGs for NP and Non-Signaling PCPs, Revisited

• [[Lalita Devadas]]
• [[Samuel B. Hopkins]]
• [[Yael Tauman Kalai]]
• [[Pravesh K. Kothari]]
• [[Alex Lombardi]]
• [[Surya Mathialagan]]

2026-01-03

• #cryptography
• #paper

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.