Paper 2025/1913 Original: eprint.iacr.org/2025/1913 ↗
Unambiguous SNARGs for P from LWE with Applications to PPAD Hardness
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
- Preprint.
- History
- 2025-10-13: last updated
- 2025-10-13: published
- Short URL
- https://ia.cr/2025/1913
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2025/1913}
}