Universal SNARGs for NP from Proofs of Completeness

We construct a succinct non-interactive argument system (SNARG) for any NP language L, and prove the non-adaptive soundness assuming the security of an FHE scheme, a batch argument (BARG) scheme, as well as the existence of any two-message argument system for L where the prover’s message is succinct, and the completeness property has a polynomial-size Extended Frege proof. Our SNARG is *universal* in the sense that the construction does not depend on the two-message argument system.

We also show how to convert any adaptively sound designated verifier SNARG into publicly verifiable SNARGs with adaptive soundness, assuming the underlying designated verifier SNARG has a polynomial-size Extended Frege proof of completeness.

Our framework yields several corollaries, including:

- a SNARG for NP with a transparent CRS and non-adaptive soundness, assuming LWE and the (non-explicit) existence of any witness encryption for NP that has a polynomial-size 'Extended Frege proof of correctness'. As a corollary, we obtain SNARGs for NP under the evasive LWE and subexponential LWE assumptions, with a (long) transparent CRS and non-adaptive soundness.

- a SNARG for UP with a long (and even transparent!) CRS and adaptive soundness under the evasive LWE and subexponential LWE assumptions.

- a SNARG for NP with a short CRS and non-adaptive soundness assuming LWE, FHE, and the (non-explicit) existence of any hash function that makes Micali's SNARG construction sound.

We prove our results by extending the encrypt-hash-and-BARG paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24]; in this work, we use Extended Frege proofs as a security reduction from one argument system to another, rather than as an outright security proof. Our universal construction suggests that the encrypt-hash-and-BARG construction can be viewed as a ``best possible SNARG''.

Based on the joint work with Yael Tauman Kalai, Alex Lombardi, and Surya Mathialagan.