Cryptography Reference
In-Depth Information
the solitary begins, the partners can no longer exchange information. The following
definition of such an interaction extends Definitions 4.2.1 and 4.2.2.
Definition 4.11.1 (Two-Partner Model):
The
two-partner model
consists of
three interactive machines, two called
partners
and the third called the
solitary
,
that are linked and interact as hereby specified:
The input tapes of all three parties coincide, and their content is called the
common
input
.
The random tapes of the two partners coincide and are called the
partners' ran-
dom tape
. (The solitary has a separate random tape.)
The solitary has two pairs of communication tapes and two switch tapes, instead
of a single pair of communication tapes and a single switch tape (as in Defini-
tion 4.2.1).
The two partners have the same identity, and the solitary has an opposite identity
(see Definitions 4.2.1 and 4.2.2).
The first (resp., second ) switch tape of the solitary coincides with the switch
tape of the first (resp., second) partner, and the first (resp., second) read-only
communication tape of the solitary coincides with the write-only communication
tape of the first (resp., second ) partner, and vice versa.
The
joint computation
of the three parties, on a common input x , is a sequence of
triplets. Each triplet consists of the local configurations of the three machines. The
behavior of each partner-solitary pair is as in the definition of the joint computation
of a pair of interactive machines.
We denote by
(
x
)
the output of the solitary S after interacting with the
partners P
1
and P
2
, on common input x .
P
1
,
P
2
,
S
4.11.1.2. Two-Prover Interactive Proofs
A two-prover interactive proof system is now defined analogously to the one-prover
case (see Definitions 4.2.4 and 4.2.6).
Definition 4.11.2 (Two-Prover Interactive Proof System):
A triplet of interac-
tive machines
(
P
1
,
P
2
,
V
)
in the two-partner model is called a
proof system for
a language
L if the machine V (called
verifier)
is probabilistic polynomial-time
and the following two conditions hold:
Completeness:
For every x
∈
L,
2
3
Pr
[
P
1
,
P
2
,
V
(
x
)
=
1]
≥
Soundness:
For every x
∈
L and every pair of partners
(
B
1
,
B
2
)
,
1
3
Pr
[
B
1
,
B
2
,
V
(
x
)
=
1]
≤
1
As usual, the error probability in both conditions can be reduced (from
3
)downto
2
−
poly(
|
x
|
)
by
sequentially
repeating the protocol sufficiently many times. Error reduction