Paper 2006/359
On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge
Mihir Bellare and Oded Goldreich
Abstract
This note points out a gap between two natural formulations of the concept of a proof of knowledge, and shows that in all natural cases (e.g., NP-statements) this gap can be closed. The aforementioned formulations differ by whether they refer to (all possible) probabilistic or deterministic prover strategies. Unlike in the rest of cryptography, in the current context, the obvious transformation of probabilistic strategies to deterministic strategies does not seem to suffice per se.
Note: Posted also on ECCC
Metadata
- Available format(s)
- PS
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Proof of KnowledgeProbabilistic Proof SystemsProbabilism versus DeterminismExpected Running Time
- Contact author(s)
- oded goldreich @ weizmann ac il
- History
- 2006-10-23: received
- Short URL
- https://ia.cr/2006/359
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2006/359,
author = {Mihir Bellare and Oded Goldreich},
title = {On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge},
howpublished = {Cryptology {ePrint} Archive, Paper 2006/359},
year = {2006},
url = {https://eprint.iacr.org/2006/359}
}
