Paper 2024/956

SNARGs under LWE via Propositional Proofs

Zhengzhong Jin, Northeastern University, Massachusetts Institute of Technology
Yael Tauman Kalai, Microsoft Research, Massachusetts Institute of Technology
Alex Lombardi, Princeton University
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Abstract

We construct a succinct non-interactive argument (SNARG) system for every NP language $\mathcal{L}$ that has a propositional proof of non-membership for each $x\notin \mathcal{L}$. The soundness of our SNARG system relies on the hardness of the learning with errors (LWE) problem. The common reference string (CRS) 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 for languages $\mathcal L$ with proof length shorter than logarithmic in the deterministic time complexity of $\mathcal L$. Our SNARG improves over prior SNARGs for such ``hard'' NP languages (Sahai and Waters, STOC 2014, Jain and Jin, FOCS 2022) in several ways: - For languages with polynomial-length propositional proofs of non-membership, our SNARGs are based on a single, polynomial-time falsifiable assumption, namely LWE. - Our construction handles propositional proofs of super-polynomial length, as long as they have bounded space, under the subexponential LWE assumption. - Our SNARGs have a transparent setup, meaning that no private randomness is required to generate the CRS. 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 $\mathsf{NP}$ witnesses. The key new idea in our cryptographic construction is what we call a ``locally unsatisfiable extension'' of the $\mathsf{NP}$ verification circuit $\{C_x\}_x$. We say that an $\mathsf{NP}$ verifier has a locally unsatisfiable extension if for every $x\not\in \mathcal L$, there exists an extension $E_x$ of $C_x$ that is not even locally satisfiable in the sense of a local assignment generator [Paneth-Rothblum, TCC 2017]. Crucially, we allow $E_x$ to be depend arbitrarily on $x$ rather than being efficiently constructible. In this work, we show -- via a ``hash-and-BARG'' for a hidden, encrypted computation -- how to build SNARGs for all languages with locally unsatisfiable extensions. We additionally show that propositional proofs of unsatisfiability generically imply the existence of locally unsatisfiable extensions, which allows us to deduce our main results. As an illustrative example, our results imply a SNARG for the decisional Diffie-Hellman (DDH) language under the LWE assumption.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. STOC 2024
DOI
10.1145/3618260.3649770
Keywords
SNARGsPropositional Proofs
Contact author(s)
zh jin @ northeastern edu
yael @ microsoft com
alex lombardi @ princeton edu
vinodv @ mit edu
History
2024-06-14: revised
2024-06-14: received
See all versions
Short URL
https://ia.cr/2024/956
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2024/956,
      author = {Zhengzhong Jin and Yael Tauman Kalai and Alex Lombardi and Vinod Vaikuntanathan},
      title = {{SNARGs} under {LWE} via Propositional Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2024/956},
      year = {2024},
      doi = {10.1145/3618260.3649770},
      note = {\url{https://eprint.iacr.org/2024/956}},
      url = {https://eprint.iacr.org/2024/956}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.