@inproceedings{80ec89e6588a4d4eaf04f8e1e78af5c2,
title = "Short Paper: Naysayer Proofs",
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 logarithmic 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.",
keywords = "blockchain, proof system, smart contract, soundness, zero-knowledge",
author = "Seres, {Istv{\'a}n Andr{\'a}s} and Noemi Glaeser and Joseph Bonneau",
note = "Publisher Copyright: {\textcopyright} International Financial Cryptography Association 2025.; 28th International Conference on Financial Cryptography and Data Security, FC 2024 ; Conference date: 04-03-2024 Through 08-03-2024",
year = "2025",
doi = "10.1007/978-3-031-78679-2_2",
language = "English (US)",
isbn = "9783031786785",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "22--32",
editor = "Jeremy Clark and Elaine Shi",
booktitle = "Financial Cryptography and Data Security - 28th International Conference, FC 2024, Revised Selected Papers",
address = "Germany",
}