Cryptography Reference
InDepth Information
extraction of the 3coloring is done by an oracle machine, called an
extractor
, that is given access to a function specifying the behavior
P
(i.e., the messages it sends in response to particular messages it may
receive). We require that the (expected) running time of the extrac
tor, on input
G
and access to an oracle specifying
P
's messages, be
inversely related (by a factor polynomial in
) to the probability
that
P
convinces
V
to accept
G
.Inthecasethat
P
always convinces
V
to accept
G
, the extractor runs in expected polynomialtime. The
same holds in case
P
convinces
V
to accept with noticeable probability.
On the other hand, in case
P
never convinces
V
to accept, essentially
nothing is required of the extractor. (We stress that the latter special
cases do not suce for a satisfactory definition; see discussion in (65,
Sec. 4.7.1).)

G

NonInteractive ZeroKnowledge.
The model of noninteractive
zeroknowledge proof systems, introduced in (29), consists of three enti
ties: a prover, a verifier and a uniformly selected
reference string
(which
can be thought of as being selected by a trusted third party). Both
the verifier and prover can read the reference string, and each can
toss additional coins. The interaction consists of a single message sent
from the prover to the verifier, who then is left with the final decision
(whether to accept or not). The (basic) zeroknowledge requirement
refers to a simulator that outputs pairs that should be computation
ally indistinguishable from the distribution (of pairs consisting of a
uniformly selected reference string and a random prover message) seen
in the real model.
9
Noninteractive zeroknowledge proof systems have
numerous applications (e.g., to the construction of publickey encryp
tion and signature schemes, where the reference string may be incorpo
rated in the publickey). Several different definitions of noninteractive
zeroknowledge proofs were considered in the literature.
9
Note that the verifier does not effect the distribution seen in the real model, and so the
basic definition of zeroknowledge does not refer to it. The verifier (or rather a process of
adaptively selecting assertions to be proved) will be referred to in the adaptive variants of
the definition.