Cryptology ePrint Archive: Report 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.
Category / Keywords: foundations / Proof of Knowledge, Probabilistic Proof Systems, Probabilism versus Determinism, Expected Running Time
Date: received 22 Oct 2006
Contact author: oded goldreich at weizmann ac il
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Note: Posted also on ECCC
Version: 20061023:072341 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]