Paper 2024/2015

Universal SNARGs for NP from Proofs of Correctness

Abstract

We give new constructions of succinct non-interactive arguments ($\mathsf{SNARG}$s) for $\mathsf{NP}$ in the settings of both non-adaptive and adaptive soundness. Our construction of non-adaptive $\mathsf{SNARG}$ is universal assuming the security of a (leveled or unleveled) fully homomorphic encryption ($\mathsf{FHE}$) scheme as well as a batch argument ($\mathsf{BARG}$) scheme. Specifically, for any choice of parameters $\ell$ and $L$, we construct a candidate $\mathsf{SNARG}$ scheme for any $\mathsf{NP}$ language $\mathcal{L}$ with the following properties: - the proof length is $\ell\cdot \mathsf{poly}(\lambda)$, - the common reference string $\mathsf{crs}$ has length $L\cdot \mathsf{poly}(\lambda)$, and - the setup is transparent (no private randomness). We prove that this $\mathsf{SNARG}$ has non-adaptive soundness assuming the existence of any $\mathsf{SNARG}$ where the proof size is $\ell$, the $\mathsf{crs}$ size is $L$, and there is a size $L$ Extended Frege ($\mathcal{EF}$) proof of completeness for the $\mathsf{SNARG}$. Moreover, we can relax the underlying $\mathsf{SNARG}$ to be any 2-message privately verifiable argument where the first message is of length $L$ and the second message is of length $\ell$. This yields new $\mathsf{SNARG}$ constructions based on any ``$\mathcal{EF}$-friendly'' designated-verifier $\mathsf{SNARG}$ or witness encryption scheme. We emphasize that our $\mathsf{SNARG}$ is universal in the sense that it does not depend on the argument system. We show several new implications of this construction that do not reference proof complexity: - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with transparent $\mathsf{crs}$ from evasive $\mathsf{LWE}$ and $\mathsf{LWE}$. This gives a candidate lattice-based $\mathsf{SNARG}$ for $\mathsf{NP}$. - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with transparent $\mathsf{crs}$ assuming the (non-explicit) existence of any $\mathsf{iO}$ and $\mathsf{LWE}$. - a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with a short and transparent (i.e., uniform) $\mathsf{crs}$ assuming $\mathsf{LWE}$, $\mathsf{FHE}$ and the (non-explicit) existence of any hash function that makes Micali's $\mathsf{SNARG}$ construction sound. - a non-adaptive $\mathsf{SNARG}$ for languages such as $\mathsf{QR}$ and $\overline{\mathsf{DCR}}$ assuming only $\mathsf{LWE}$. In the setting of adaptive soundness, we show how to convert any designated verifier $\mathsf{SNARG}$ into publicly verifiable $\mathsf{SNARG}$, assuming the underlying designated verifier $\mathsf{SNARG}$ has an $\mathcal{EF}$ proof of completeness. As a corollary, we construct an adaptive $\mathsf{SNARG}$ for $\mathsf{UP}$ with a transparent $\mathsf{crs}$ assuming subexponential $\mathsf{LWE}$ and evasive $\mathsf{LWE}$. We prove our results by extending the encrypt-hash-and-$\mathsf{BARG}$ paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24].