Paper 2025/2328

SNARGs for NP via Fiat–Shamir in the Plain Model

Abstract

We study constructions of succinct non-interactive arguments (SNARGs) for $\mathsf{NP}$ in the standard model. Specifically, we revisit the seminal Micali transformation (applying Fiat--Shamir to Kilian's protocol), which has traditionally only been analyzed in the random oracle model. We show that the Micali framework can be successfully instantiated in the standard model by leveraging a new interaction between two primitives: a PCP satisfying a property we term \emph{shadow soundness}, and a vector commitment scheme satisfying \emph{function statistical binding}. We prove that any language in $\mathsf{NP}$ admits a shadow PCP algorithm in the class $\mathsf{NC}$. Combining such a PCP with a vector commitment with function-statistical-binding for $\mathsf{NC}$ yields a secure SNARG, under the assumption of sub-exponential hardness of LWE. Our results refute "universal" attacks on the Micali framework by exhibiting a large family of concrete instantiations of the underlying components for which the transformation is sound.