Paper 2024/165
Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Abstract
A succinct non-interactive argument (SNARG) for $\mathsf{NP}$ allows a prover to convince a verifier that an $\mathsf{NP}$ statement $x$ is true with a proof of size $o(|x| + |w|)$, where $w$ is the associated $\mathsf{NP}$ witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for $\mathsf{NP}$ in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions, and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for $\mathsf{NP}$ from falsifiable assumptions. All previous SNARGs for $\mathsf{NP}$ in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters).
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- succinct non-interactive argumentsSNARGsadaptive soundness
- Contact author(s)
-
bwaters @ cs utexas edu
dwu4 @ cs utexas edu - History
- 2024-02-06: approved
- 2024-02-05: received
- See all versions
- Short URL
- https://ia.cr/2024/165
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/165,
author = {Brent Waters and David J. Wu},
title = {Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation},
howpublished = {Cryptology ePrint Archive, Paper 2024/165},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/165}},
url = {https://eprint.iacr.org/2024/165}
}
