Paper 2023/1472 Original: eprint.iacr.org/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.
- History
- 2025-02-16: last updated
- 2023-09-25: published
- Short URL
- https://ia.cr/2023/1472
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}