On Probabilistic versus Deterministic Provers
in the Definition of Proofs Of Knowledge
Webpage for a paper by Bellare and 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.
This note refers to and is heavily based on the definition
(of proofs of knowledge) that was put forward in our paper
On defining
proofs of knowledge (1992).
Material available on-line
- First version posted:
Oct.
2006.
- Revisions: none yet.
Back to
either Oded Goldreich's homepage.
or general list of papers.