International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge

Authors:
Mihir Bellare
Oded Goldreich
Download:
URL: http://eprint.iacr.org/2006/359
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2006-21850,
  title={On Probabilistic versus Deterministic Provers in the Definition of Proofs Of Knowledge},
  booktitle={IACR Eprint archive},
  keywords={foundations /  Proof of Knowledge, Probabilistic Proof Systems, Probabilism versus Determinism, Expected Running Time},
  url={http://eprint.iacr.org/2006/359},
  note={ oded.goldreich@weizmann.ac.il 13443 received 22 Oct 2006},
  author={Mihir Bellare and Oded Goldreich},
  year=2006
}