Zhengzhong Jin: Universal SNARGs for NP from Proofs of Completeness
Speaker
Zhengzhong Jin (Northeastern University)
Host
Vinod Vaikuntanathan & Yael Kalai
We construct a succinct non-interactive argument system (SNARG) for any NP language L, and prove the non-adaptive soundness assuming the security of an FHE scheme, a batch argument (BARG) scheme, as well as the existence of any two-message argument system for L where the prover’s message is succinct, and the completeness property has a polynomial-size Extended Frege proof. Our SNARG is *universal* in the sense that the construction does not depend on the two-message argument system.
We also show how to convert any adaptively sound designated verifier SNARG into publicly verifiable SNARGs with adaptive soundness, assuming the underlying designated verifier SNARG has a polynomial-size Extended Frege proof of completeness.
Our framework yields several corollaries, including:
- a SNARG for NP with a transparent CRS and non-adaptive soundness, assuming LWE and the (non-explicit) existence of any witness encryption for NP that has a polynomial-size 'Extended Frege proof of correctness'. As a corollary, we obtain SNARGs for NP under the evasive LWE and subexponential LWE assumptions, with a (long) transparent CRS and non-adaptive soundness.
- a SNARG for UP with a long (and even transparent!) CRS and adaptive soundness under the evasive LWE and subexponential LWE assumptions.
- a SNARG for NP with a short CRS and non-adaptive soundness assuming LWE, FHE, and the (non-explicit) existence of any hash function that makes Micali's SNARG construction sound.
We prove our results by extending the encrypt-hash-and-BARG paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24]; in this work, we use Extended Frege proofs as a security reduction from one argument system to another, rather than as an outright security proof. Our universal construction suggests that the encrypt-hash-and-BARG construction can be viewed as a ``best possible SNARG''.
Based on the joint work with Yael Tauman Kalai, Alex Lombardi, and Surya Mathialagan.
We also show how to convert any adaptively sound designated verifier SNARG into publicly verifiable SNARGs with adaptive soundness, assuming the underlying designated verifier SNARG has a polynomial-size Extended Frege proof of completeness.
Our framework yields several corollaries, including:
- a SNARG for NP with a transparent CRS and non-adaptive soundness, assuming LWE and the (non-explicit) existence of any witness encryption for NP that has a polynomial-size 'Extended Frege proof of correctness'. As a corollary, we obtain SNARGs for NP under the evasive LWE and subexponential LWE assumptions, with a (long) transparent CRS and non-adaptive soundness.
- a SNARG for UP with a long (and even transparent!) CRS and adaptive soundness under the evasive LWE and subexponential LWE assumptions.
- a SNARG for NP with a short CRS and non-adaptive soundness assuming LWE, FHE, and the (non-explicit) existence of any hash function that makes Micali's SNARG construction sound.
We prove our results by extending the encrypt-hash-and-BARG paradigm of [Jin-Kalai-Lombardi-Vaikuntanathan, STOC '24]; in this work, we use Extended Frege proofs as a security reduction from one argument system to another, rather than as an outright security proof. Our universal construction suggests that the encrypt-hash-and-BARG construction can be viewed as a ``best possible SNARG''.
Based on the joint work with Yael Tauman Kalai, Alex Lombardi, and Surya Mathialagan.