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.