Welcome to the resource topic for 2024/2015
Title:
Universal SNARGs for NP from Proofs of Correctness
Authors: Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Surya Mathialagan
Abstract:We give new constructions of succinct non-interactive arguments ($\mathsf{SNARG}s) for \mathsf{NP}$ in the settings of both non-adaptive and adaptive soundness.
Our construction of non-adaptive \mathsf{SNARG} is universal assuming the security of a (leveled or unleveled) fully homomorphic encryption (\mathsf{FHE}) scheme as well as a batch argument (\mathsf{BARG}) scheme. Specifically, for any choice of parameters \ell and L, we construct a candidate \mathsf{SNARG} scheme for any \mathsf{NP} language \mathcal{L} with the following properties:
- the proof length is $\ell\cdot \mathsf{poly}(\lambda)$,
- the common reference string $\mathsf{crs}$ has length $L\cdot \mathsf{poly}(\lambda)$, and
- the setup is transparent (no private randomness).
We prove that this \mathsf{SNARG} has non-adaptive soundness assuming the existence of any \mathsf{SNARG} where the proof size is \ell, the \mathsf{crs} size is L, and there is a size L Extended Frege (\mathcal{EF}) proof of completeness for the \mathsf{SNARG}.
Moreover, we can relax the underlying \mathsf{SNARG} to be any 2-message privately verifiable argument where the first message is of length L and the second message is of length \ell. This yields new \mathsf{SNARG} constructions based on any ``\mathcal{EF}-friendly’’ designated-verifier \mathsf{SNARG} or witness encryption scheme. We emphasize that our \mathsf{SNARG} is universal in the sense that it does not depend on the argument system.
We show several new implications of this construction that do not reference proof complexity:
- a non-adaptive $\mathsf{SNARG}$ for $\mathsf{NP}$ with transparent $\mathsf{crs}$ from evasive $\mathsf{LWE}$ and $\mathsf{LWE}$. This gives a candidate lattice-based $\mathsf{SNARG}$ for $\mathsf{NP}$.
- a non-adaptive \mathsf{SNARG} for \mathsf{NP} with transparent \mathsf{crs} assuming the (non-explicit) existence of any \mathsf{iO} and \mathsf{LWE}.
- a non-adaptive \mathsf{SNARG} for \mathsf{NP} with a short and transparent (i.e., uniform) \mathsf{crs} assuming \mathsf{LWE}, \mathsf{FHE} and the (non-explicit) existence of any hash function that makes Micali’s \mathsf{SNARG} construction sound.
- a non-adaptive \mathsf{SNARG} for languages such as \mathsf{QR} and \overline{\mathsf{DCR}} assuming only \mathsf{LWE}.
In the setting of adaptive soundness, we show how to convert any designated verifier \mathsf{SNARG} into publicly verifiable \mathsf{SNARG}, assuming the underlying designated verifier \mathsf{SNARG} has an \mathcal{EF} proof of completeness. As a corollary, we construct an adaptive \mathsf{SNARG} for \mathsf{UP} with a transparent \mathsf{crs} assuming subexponential \mathsf{LWE} and evasive \mathsf{LWE}.
We prove our results by extending the encrypt-hash-and-\mathsf{BARG} paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24].
ePrint: https://eprint.iacr.org/2024/2015
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .