Paper 2023/1472
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 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: We addressed an issue in our main theorem.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Published elsewhere. Minor revision. Financial Cryptography and Data Security 2024
- Keywords
- proof systemzero-knowledgesoundnessblockchainsmart contract
- Contact author(s)
-
seresistvanandras @ gmail com
nglaeser @ umd edu
jbonneau @ gmail com - History
- 2024-03-14: last of 2 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},
url = {https://eprint.iacr.org/2023/1472}
}