You are looking at a specific version 20061023:072341 of this paper. See the latest version.

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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.