Paper 2024/1060
Quirky Interactive Reductions of Knowledge
Abstract
Interactive proofs and arguments of knowledge can be generalized to the concept of interactive reductions of knowledge, where proving knowledge of a witness for one NP language is reduced to proving knowledge of a witness for another NP language. We take this generalization and specialize it to a class of reductions we refer to as `quirky interactive reductions of knowledge' (or QUIRKs). This name reflects our particular design choices within the broad and diverse world of interactive reduction methods. A central design choice is allowing the prover to rewind or regress to any previous reduction and repeat it as many times as desired. We prove completeness and extractability properties for QUIRKs. We also offer tools for constructing extraction algorithms along with several simple examples of usage.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- knowledge soundnessreductions of knowledgeproofs of knowledge
- Contact author(s)
- josephljohnston @ mac com
- History
- 2024-06-30: approved
- 2024-06-29: received
- See all versions
- Short URL
- https://ia.cr/2024/1060
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1060,
author = {Joseph Johnston},
title = {Quirky Interactive Reductions of Knowledge},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1060},
year = {2024},
url = {https://eprint.iacr.org/2024/1060}
}
