Cryptography Reference
In-Depth Information
extraction of the 3-coloring 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 polynomial-time. 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
|
Non-Interactive Zero-Knowledge.
The model of non-interactive
zero-knowledge 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) zero-knowledge 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
Non-interactive zero-knowledge proof systems have
numerous applications (e.g., to the construction of public-key encryp-
tion and signature schemes, where the reference string may be incorpo-
rated in the public-key). Several different definitions of non-interactive
zero-knowledge 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 zero-knowledge 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.
