Adaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation

Brent Waters; David J. Wu

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 $NP$ allows a prover to convince a verifier that an $NP$ statement $x$ is true with a proof of size $o (| x | + | w |)$ , where $w$ is the associated $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 $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 from falsifiable assumptions. All previous SNARGs for 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 arguments SNARGs adaptive 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},
      url = {https://eprint.iacr.org/2024/165}
}