SNARGs, Propositional Proofs, and Local Unsatisfiability

Speaker: Alex Lombardi , Princeton

Date: Friday, December 08, 2023

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location:

Event Type: Seminar

Room Description: G-882

Host: Vinod Vaikuntanathan , CSAIL MIT

Contact: Vinod Vaikuntanathan, vinodv@csail.mit.edu

Relevant URL: https://toc.csail.mit.edu/node/1605

Speaker URL: https://sites.google.com/view/alex-lombardi/home

Speaker Photo:

Reminders to: cis-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Alex Lombardi: SNARGs, Propositional Proofs, and Local Unsatisfiability

Abstract:

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.

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.

Research Areas:
Security & Cryptography

Impact Areas:
Cybersecurity

See other events that are part of the CIS Seminar Series 2023 - 2024.

Created by Vinod Vaikuntanathan at Wednesday, December 06, 2023 at 8:08 AM.