Cryptography Reference
In-Depth Information
zero-knowledge. Furthermore, assuming the existence of families of trapdoor
permutations, the prover strategy in such a proof system can be implemented by
a probabilistic polynomial-time machine that gets an
NP
-witness as auxiliary
input.
The “furthermore” statement extends to a model that allows the adaptive selection of
polynomially many assertions (i.e., a model that combines the two extensions discussed
in this subsection).
4.11.
∗
Multi-Prover Zero-Knowledge Proofs
In this section we consider an extension of the notion of an interactive proof system.
Specifically, we consider the interaction of a verifier with more than one prover (say,
two provers). The provers can share an a-priori-selected strategy, but it is assumed that
they cannot interact with each other during the time period in which they interact with
the verifier. Intuitively, the provers can coordinate their strategies prior to, but not dur-
ing, their interrogation by the verifier. Indeed, the multi-prover model is reminiscent
of the common police procedure of isolating suspected collaborators and interrogating
each of them separately. We discuss one realistic (digital) setting in which this model
is applicable.
The notion of a multi-prover interactive proof plays a fundamental role in complexity
theory. That aspect is not addressed here. In the current section we merely address the
zero-knowledge aspects of multi-party interactive proofs. Most importantly, the multi-
prover model enables the construction of (perfect) zero-knowledge proof systems for
NP
,
independent of any complexity-theoretic assumptions
.
4.11.1. Definitions
For the sake of simplicity, we consider the two-prover model. We remark that the use
of more provers would not offer any essential advantages (and specifically, none that
would interest us in this section). Loosely speaking, a two-prover interactive proof
system is a three-party protocol in which two parties are provers and the additional
party is a verifier. The only interaction allowed in this model is between the verifier
and each of the provers individually. In particular, a prover does not “know” the con-
tent of the messages sent by the verifier to the other prover. The provers do, however,
share a random-input tape that is (as in the one-prover case) “beyond the reach” of the
verifier. The two-prover setting is a special case of the
two-partner model
described
next.
4.11.1.1. The Two-Partner Model
The two-partner model consists of two
partners
interacting with a third party, called
the
solitary
. The two partners can agree on their strategies beforehand, and in particular
they can agree on a common uniformly chosen string. Yet once the interaction with
