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).)
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.
Search WWH ::

Custom Search