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 (SNARGs) for NP 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].

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Contact author(s)
zh jin @ northeastern edu
tauman @ mit edu
alex lombardi @ princeton edu
smathi @ mit edu
History
2024-12-13: approved
2024-12-13: received
See all versions
Short URL
https://ia.cr/2024/2015
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/2015,
      author = {Zhengzhong Jin and Yael Tauman Kalai and Alex Lombardi and Surya Mathialagan},
      title = {Universal {SNARGs} for {NP} from Proofs of Correctness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2015},
      year = {2024},
      url = {https://eprint.iacr.org/2024/2015}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.