Paper 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. The size of the proof and CRS for a batch of $k$ statements grows only with the size of a *single* witness.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- SNARGsDelegation schemesBatch arguments
- Contact author(s)
- achoud @ cs jhu edu,abhishek @ cs jhu edu,zjin12 @ jhu edu
- History
- 2021-11-08: revised
- 2021-06-16: received
- See all versions
- Short URL
- https://ia.cr/2021/808
- License
-
CC BY