Paper 2024/165

Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation

Brent Waters, The University of Texas at Austin, NTT Research
David J. Wu, The University of Texas at Austin
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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2024/165}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.