Cryptology ePrint Archive: Report 2021/808

SNARGs for $\mathcal{P}$ from LWE

Arka Rai Choudhuri and Abhishek Jain and Zhengzhong Jin

Abstract: We provide the first construction of a succinct non-interactive argument (SNARG) for *all* polynomial time deterministic computations based on standard assumptions. For $T$ steps of computation, the size of the proof and the common random string (CRS) as well as the verification time are poly-logarithmic in $T$. The security of our scheme relies on the hardness of the Learning with Errors (LWE) problem against polynomial-time adversaries. Previously, SNARGs based on standard assumptions could support bounded-depth computations and required sub-exponential hardness assumptions [Jawale-Kalai-Khurana-Zhang, STOC'21].

Along the way, we also provide the first construction of non-interactive batch arguments for $\mathsf{NP}$ based solely on the LWE assumption.

Category / Keywords: foundations / SNARGs, Delegation schemes, Batch arguments

Original Publication (with minor differences): FOCS 2021

Date: received 14 Jun 2021, last revised 8 Nov 2021

Contact author: achoud at cs jhu edu, abhishek at cs jhu edu, zjin12 at jhu edu

Available format(s): PDF | BibTeX Citation

Version: 20211108:181325 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]