Cryptography Reference
In-Depth Information
of the interactive proof of Figure 4.2 cannot be simulated in a black-
box manner (unless
NP
is contained in
BPP
(71))
implies
that this
version is not zero-knowledge (as per Definition 4.1 itself). However,
the (underlying) belief that any zero-knowledge protocol can be sim-
ulated in a black-box manner was refuted recently by Barak (8). For
further discussion, see Section 4.4.4.
Honest verifier versus general cheating verifier.
Definition 4.1
refers to all feasible verifier strategies, which is most natural (in the
cryptographic setting) because zero-knowledge is supposed to cap-
ture the robustness of the prover under
any feasible
(i.e., adversarial)
attempt to gain something by interacting with it. A weaker and still
interesting notion of zero-knowledge refers to what can be gained by
an “honest verifier” (or rather a semi-honest verifier)
6
that interacts
with the prover as directed, with the exception that it may maintain
(and output) a record of the entire interaction (i.e., even if directed
to erase all records of the interaction). Although such a weaker notion
is not satisfactory for standard cryptographic applications, it yields a
fascinating notion from a conceptual as well as a complexity-theoretic
point of view. Furthermore, as shown in (77; 122), every proof system
that is
zero-knowledge with respect to the honest-verifier
can be trans-
formed into a
standard zero-knowledge
proof (without using intractabil-
ity assumptions and in the case of “public-coin” proofs this is done
without significantly increasing the prover's computational effort).
Statistical versus Computational Zero-Knowledge.
Recall that
Definition 4.1 postulates that for every probability ensemble of one type
(i.e., representing the verifier's output after interaction with the prover)
there exists a “similar” ensemble of a second type (i.e., representing
the simulator's output). One key parameter is the interpretation of
“similarity”. Three interpretations, yielding different notions of zero-
6
The term “honest verifier” is more appealing when considering an alternative (equivalent)
formulation of Definition 4.1. In the alternative definition (see (65, Sec. 4.3.1.3)), the
simulator is “only” required to generate the verifier's view of the real interaction, where
the verifier's view includes its (common and auxiliary) inputs, the outcome of its coin
tosses, and all messages it has received.
