Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness

Liyan Chen; Cody Freitag; Zhengzhong Jin; Daniel Wichs

Paper 2025/1913

Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness

Liyan Chen

, Massachusetts Institute of Technology

Cody Freitag

, Northeastern University

Zhengzhong Jin

, Northeastern University

Daniel Wichs

, Northeastern University, NTT Research

Abstract

We construct the first unambiguous succinct non-interactive arguments (SNARGs) for P and incrementally verifiable computation (IVC) for P from the polynomial hardness of learning with errors (LWE). Unambiguity guarantees that it is computationally hard to find two distinct accepting proofs for the same statement. As an application, we establish the first PPAD hardness result based on the polynomial hardness of LWE combined with a widely believed complexity assumption. Central to our approach is a new notion of rate-1 witness-unambiguous batch arguments for NP, which we give the first construction from the polynomial hardness of LWE. This notion may be of independent interest.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. STOC 2025
DOI: https://doi.org/10.1145/3717823.3718159
Keywords: SNARGs PPAD Batch Arguments
Contact author(s): cliyan @ mit edu
c freitag @ northeastern edu
zh jin @ northeastern edu
wichs @ ccs neu edu
History: 2025-10-17: approved; 2025-10-13: received; See all versions
Short URL: https://ia.cr/2025/1913
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1913,
      author = {Liyan Chen and Cody Freitag and Zhengzhong Jin and Daniel Wichs},
      title = {Unambiguous {SNARGs} for P from {LWE} with Applications to {PPAD} Hardness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1913},
      year = {2025},
      doi = {https://doi.org/10.1145/3717823.3718159},
      url = {https://eprint.iacr.org/2025/1913}
}