Paper 2025/2328

Micali’s SNARG, Function Vector Commitments, and Fiat–Shamir

Abstract

Micali's construction of succinct non-interactive arguments (SNARGs) combines a probabilistically checkable proof (PCP), a vector commitment, and the Fiat--Shamir transformation. Its security is established in the random oracle model, but replacing the random oracle with an explicit hash function presents a fundamental challenge: Fiat--Shamir can fail for interactive arguments, and certain choices of the commitment scheme make Micali's construction unsound for every instantiation of the Fiat--Shamir hash. We show how to instantiate Micali's construction in the standard model assuming LWE and function vector commitments with \emph{function statistical binding} for $\Ppoly$, obtaining a non-adaptively sound SNARG for $\NP$. Our construction combines such a commitment with an LWE-based correlation-intractaxble hash and a PCP satisfying a new property, \emph{shadow soundness}. A PCP shadow is a short digest that preserves the information needed to determine the verifier's decision. By statistically binding the commitment to this shadow, we obtain the sparse relation needed to prove Fiat--Shamir soundness. We construct shadow PCPs for $\NP$ whose shadow algorithms lie in $\NC$, and we give a feasibility instantiation of the commitment scheme from strong assumptions. Our results thus identify a concrete cryptographic target for instantiating Micali's SNARG under weaker assumptions, and show that the framework does not admit an attack that succeeds for every choice of its components.