Friday, December 8, 2023 - 10:30am to 12:00pm

Location:

G-882 Hewlett Room

Speaker:

Alex Lombardi

We construct a succinct non-interactive argument system for every NP language L that has a propositional proof of non-membership, i.e. that a string x is *not* in L, and prove it is non-adaptively sound under the LWE assumption. The common reference string in our construction grows with the *space* required to verify the propositional proof, and the size of the proof grows *poly-logarithmically *in the length of the propositional proof.

Unlike most of the literature on SNARGs, our result implies SNARGs with proof length shorter than logarithmic in the deterministic time complexity of the language. As an illustrative example, our results imply a SNARG for the decisional Diffie-Hellman (DDH) language under the LWE assumption.

Unlike most of the literature on SNARGs, our result implies SNARGs with proof length shorter than logarithmic in the deterministic time complexity of the language. As an illustrative example, our results imply a SNARG for the decisional Diffie-Hellman (DDH) language under the LWE assumption.

Our argument system achieves several properties unachievable by related prior work [Sahai-Waters, STOC '14, and Jain-Jin, FOCS '22] such as transparent setup and reliance on a polynomial-time falsifiable assumption. Moreover, our approach departs dramatically from these prior works: we show how to design SNARGs for hard languages without publishing a program (in the CRS) that has the power to verify NP witnesses. At a technical level, we make use of a new notion that we call a ``locally unsatisfiable extension'' of an NP verification circuit C, which is an instance-dependent extension of the circuit C that is ``locally unsatisfiable'' (in the sense of a local assignment generator) for any false statement x.