SNARGs under LWE via Propositional Proofs
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155720 |
| _version_ | 1811074739671662592 |
|---|---|
| author | Jin, Zhengzhong Kalai, Yael Lombardi, Alex Vaikuntanathan, Vinod |
| author_facet | Jin, Zhengzhong Kalai, Yael Lombardi, Alex Vaikuntanathan, Vinod |
| author_sort | Jin, Zhengzhong |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T09:54:36Z |
| format | Article |
| id | mit-1721.1/155720 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:54:36Z |
| publishDate | 2024 |
| publisher | ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing |
| record_format | dspace |
| spelling | mit-1721.1/1557202024-07-20T03:47:26Z SNARGs under LWE via Propositional Proofs Jin, Zhengzhong Kalai, Yael Lombardi, Alex Vaikuntanathan, Vinod STOC ’24, June 24–28, 2024, Vancouver, BC, Canada We construct a succinct non-interactive argument (SNARG) system for every NP language L that has a propositional proof of nonmembership, i.e. of ∉ 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 L with proof length shorter than logarithmic in the deterministic time complexity of 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: 1) For languages with polynomial-length propositional proofs of non-membership, our SNARGs are based on a single, polynomialtime falsi able assumption, namely LWE. 2) Our construction handles super-polynomial length propositional proofs, as long as they have bounded space, under the subexponential LWE assumption. 3) 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 NP witnesses. The key new idea in our construction is what we call a “locally unsatis able extension” of the NP veri cation circuit { } . We say that an NP veri er has a locally unsatis able extension if for every ∉ L, there exists an extension of that is not even locally satis able in the sense of a local assignment generator [Paneth-Rothblum, TCC 2017]. Crucially, we allow to be depend arbitrarily on rather than being e ciently constructible. 2024-07-19T15:36:45Z 2024-07-19T15:36:45Z 2024-06-10 2024-07-01T07:51:38Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155720 Jin, Zhengzhong, Kalai, Yael, Lombardi, Alex and Vaikuntanathan, Vinod. 2024. "SNARGs under LWE via Propositional Proofs." PUBLISHER_CC en 10.1145/3618260.3649770 Creative Commons Attribution-ShareAlike https://creativecommons.org/licenses/by-sa/4.0/ The author(s) application/pdf ACM|Proceedings of the 56th Annual ACM Symposium on Theory of Computing Association for Computing Machinery |
| spellingShingle | Jin, Zhengzhong Kalai, Yael Lombardi, Alex Vaikuntanathan, Vinod SNARGs under LWE via Propositional Proofs |
| title | SNARGs under LWE via Propositional Proofs |
| title_full | SNARGs under LWE via Propositional Proofs |
| title_fullStr | SNARGs under LWE via Propositional Proofs |
| title_full_unstemmed | SNARGs under LWE via Propositional Proofs |
| title_short | SNARGs under LWE via Propositional Proofs |
| title_sort | snargs under lwe via propositional proofs |
| url | https://hdl.handle.net/1721.1/155720 |
| work_keys_str_mv | AT jinzhengzhong snargsunderlweviapropositionalproofs AT kalaiyael snargsunderlweviapropositionalproofs AT lombardialex snargsunderlweviapropositionalproofs AT vaikuntanathanvinod snargsunderlweviapropositionalproofs |