Paper 2024/2015
Universal SNARGs for NP from Proofs of Correctness
Zhengzhong Jin, Northeastern University
Yael Tauman Kalai, Massachusetts Institute of Technology
Alex Lombardi, Princeton University
Surya Mathialagan, Massachusetts Institute of Technology
Abstract
We give new constructions of succinct non-interactive arguments (s) for in the settings of both non-adaptive and adaptive soundness.
Our construction of non-adaptive is universal assuming the security of a (leveled or unleveled) fully homomorphic encryption () scheme as well as a batch argument () scheme. Specifically, for any choice of parameters and , we construct a candidate scheme for any language with the following properties:
- the proof length is ,
- the common reference string has length , and
- the setup is transparent (no private randomness).
We prove that this has non-adaptive soundness assuming the existence of any where the proof size is , the size is , and there is a size Extended Frege () proof of completeness for the .
Moreover, we can relax the underlying to be any 2-message privately verifiable argument where the first message is of length and the second message is of length . This yields new constructions based on any ``-friendly'' designated-verifier or witness encryption scheme. We emphasize that our 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 for with transparent from evasive and . This gives a candidate lattice-based for .
- a non-adaptive for with transparent assuming the (non-explicit) existence of any and .
- a non-adaptive for with a short and transparent (i.e., uniform) assuming , and the (non-explicit) existence of any hash function that makes Micali's construction sound.
- a non-adaptive for languages such as and assuming only .
In the setting of adaptive soundness, we show how to convert any designated verifier into publicly verifiable , assuming the underlying designated verifier has an proof of completeness. As a corollary, we construct an adaptive for with a transparent assuming subexponential and evasive .
We prove our results by extending the encrypt-hash-and- paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24].