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




Custom Search