Naysayer proofs

István András Seres; Noemi Glaeser; Joseph Bonneau

Paper 2023/1472

Naysayer proofs

István András Seres

, Eötvös Loránd University

Noemi Glaeser

, University of Maryland, College Park, Max Planck Institute for Security and Privacy

Joseph Bonneau, a16z crypto research, New York University

Abstract

This work introduces the notion of naysayer proofs. We observe that in numerous (zero-knowledge) proof systems, it is significantly more efficient for the verifier to be convinced by a so-called naysayer that a false proof is invalid than it is to check that a genuine proof is valid. We show that every NP language has constant-size and constant-time naysayer proofs. We also show practical constructions for several example proof systems, including FRI polynomial commitments, post-quantum secure digital signatures, and verifiable shuffles. Naysayer proofs enable an interesting new optimistic verification mode potentially suitable for resource-constrained verifiers, such as smart contracts.

Note: Updated and improved the syntax and security definitions for naysayer proofs; added details to clarify the main theorem and the example constructions.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Major revision. Financial Cryptography and Data Security 2024
DOI: 10.1007/978-3-031-78679-2_2
Keywords: proof system zero-knowledge soundness blockchain smart contract
Contact author(s): seresistvanandras @ gmail com
nglaeser @ umd edu
jbonneau @ gmail com
History: 2025-02-16: last of 4 revisions; 2023-09-25: received; See all versions
Short URL: https://ia.cr/2023/1472
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1472,
      author = {István András Seres and Noemi Glaeser and Joseph Bonneau},
      title = {Naysayer proofs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1472},
      year = {2023},
      doi = {10.1007/978-3-031-78679-2_2},
      url = {https://eprint.iacr.org/2023/1472}
}