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.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- proof systemzero-knowledgesoundnessblockchainsmart contract
- Contact author(s)
-
seresistvanandras @ gmail com
nglaeser @ umd edu
jbonneau @ gmail com - History
- 2023-10-06: revised
- 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}, note = {\url{https://eprint.iacr.org/2023/1472}}, url = {https://eprint.iacr.org/2023/1472} }