On the Impossibility of SNARGs with Short CRS : (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting)

2025-12-14

We study the inherent barriers to constructing non-adaptively sound succinct non-interactive arguments (SNARGs) for NP with a CRS whose length is sublinear in the witness length. Our results cover both the standard SNARGs and SNARGs with an additional updatable feature (i.e. incrementally verifiable computation for NP).•For updatable SNARGs, we show a black-box separation from falsifiable assumptions for uniform polynomial-time reductions, assuming sub-exponential hardness of learning with error.•For general SNARGs, we show a black-box separation from falsifiable assumptions for non-uniform polynomial-time reductions that only make one query to the adversary, assuming the existence of sub-exponentially secure super-bit generators. We observe that all known SNARG constructions from polynomial hardness of standard assumptions have 1-query soundness reductions. Thus, our result complements existing constructions.Previously, the seminal work [Gentry-Wichs, STOC’11] showed a black-box separation of SNARGs from falsifiable assumptions in the adaptive soundness setting. We explore whether any barriers exist in the non-adaptive setting. To obtain our result, we derive a simulation lemma for unbounded polynomial-length auxiliary inputs assuming super-bit generators.

Succinct Non-interactive Arguments of Proximity

2025-06-15

Sometimes-Decryptable Homomorphic Encryption from Sub-exponential DDH

Lecture notes in computer science · 2025-01-01

Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness

2025-06-15 · 1 citations

On Succinct Obfuscation via Propositional Proofs

2025-12-14 · 1 citations

A central line of inquiry in the study of indistinguishability obfuscation (IO) is to minimize the size of the obfuscation. Today we know how to obfuscate programs represented as Turing machines, where the size of the obfuscation grows only with the input size and not with the machine’s running time. Jain and Jin [FOCS 2022] showed how to remove the dependency on the input size for functionally equivalent programs where equivalence can be proven in Cook’s theory PV. In this work we investigate the limits of the pursuit of succinct obfuscation. We consider the task of obfuscating a program with a large description, most of which can be made public while some portion of the description is secret. We put forth a new notion of fully succinct IO where the size of obfuscated program only grows with the size of the program’s secret part and not with the public part or with the input size. Starting with input-succinct IO for PV-equivalent machines, which is known from super-polynomially hard IO for circuits and LWE, we construct fully succinct IO for the same class of programs. We refer to such an obfuscation as fully succinct pv-IO. Next, we show how to bootstrap our fully succinct $\mathbf{p v}$-IO to achieve full IO security. Our bootstrapping theorems are based on succinct cryptographic primitives with seemingly weaker functionality: either succinct witness encryption or SNARGs for NP with unique proofs. We also require that the correctness of these primitives can be proven in theory PV. We show that these assumptions are sufficient and necessary. We demonstrate several applications of fully succinct IO and pv-IO:(i)We give the first IO construction where the size of the obfuscated program is less than twice the size of the original program for a large class of useful programs.(ii)We show how to avoid padding the program before obfuscating it – a step often necessitated by security analysis – by replacing the padding with a public random string.(iii)We give the first construction of succinct computational secret sharing for access structures represented by polynomial-size monotone circuits where the share size does not grow with the size of the access structure.

Universal SNARGs for NP from Proofs of Correctness

2025-06-15 · 2 citations

STOC ’25, Prague, Czechia

Non-interactive Zero-Knowledge from LPN and MQ

Lecture notes in computer science · 2024-01-01 · 6 citations

SNARGs under LWE via Propositional Proofs

2024-06-10 · 6 citations

We construct a succinct non-interactive argument (SNARG) system for every NP language L that has a propositional proof of non-membership, i.e. of x∉ 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, polynomial-time falsifiable 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 unsatisfiable extension” of the NP verification circuit {Cx}x. We say that an NP verifier has a locally unsatisfiable extension if for every x∉L, there exists an extension Ex of Cx that is not even locally satisfiable in the sense of a local assignment generator [Paneth-Rothblum, TCC 2017]. Crucially, we allow Ex 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.

A Note on Non-interactive Zero-Knowledge from CDH

Lecture notes in computer science · 2023-01-01 · 4 citations

Credibility in Private Set Membership

Lecture notes in computer science · 2023-01-01 · 1 citations