Cryptography Reference
In-Depth Information
)
defined as
g
(
n
)
def
The function
g
(
−
s
(
n
)
is called the
acceptance gap
of
(
P
,
V
)
, and the function
e
(
·
)
, defined as
e
(
n
)
def
·
=
c
(
n
)
=
max
{
1
−
c
(
n
)
,
s
(
n
)
}
, is called
the
error probability
of
(
P
,
V
)
. In particular,
s
is the
soundness error
of
(
P
,
V
)
,
and
1
−
c
is its
completeness error
.
We stress that
c
is a lower bound, whereas
s
is an upper bound.
Proposition 4.2.7:
The following three conditions are equivalent:
∈
IP
1.
L
. Namely, there exists an interactive proof system, with completeness bound
2
3
1
3
, for the language L.
2.
L
has very strong interactive proof systems:
For every polynomial p
(
and soundness bound
)
, there exists
an interactive proof system for the language L, with error probability bounded
above by
2
−
p
(
·
)
.
3.
L
has a very weak interactive proof:
There exists a polynomial p
(
·
)
and a gener-
alized interactive proof system for the language L, with acceptance gap bounded
below by
1
·
)
. Furthermore, completeness and soundness bounds for this sys-
tem, namely, the values
c
(
n
)
and
s
(
n
)
, can be computed in time polynomial in n.
/
p
(
·
Clearly, either of the first two items implies the third one (including the requirement for
efficiently computable bounds). The ability to efficiently compute completeness and
soundness bounds is used in proving the opposite (non-trivial) direction. The proof is
left as an exercise (i.e., Exercise 1).
)
All examples of interactive proof systems presented thus far have been degenerate
(e.g., the interaction, if any, has been unidirectional). We now present an example of a
non-degenerate interactive proof system. Furthermore, we present an interactive proof
system for a language
not known to be in
4.2.2. An Example (Graph Non-Isomorphism in
IIIP
. Specifically, the language is the
set of
pairs of non-isomorphic graphs
, denoted
GNI
. The idea underlying this proof
system is presented through the following story:
Petra von Kant claims that Goldstar
4
beer in large bottles tastes different than
Goldstar beer in small bottles. Virgil does not believe her. To prove her claim,
Petra and Virgil repeat the following process a number of times sufficient to
convince Virgil beyond reasonable doubt.
Virgil selects at random either a large bottle or a small one and pours some
beer into a tasting glass, without Petra seeing which bottle he uses. Virgil then
hands Petra the glass and asks her to tell which of the bottles he has used.
If Petra never errs in her answers, then Virgil is convinced of the validity of
her claim. (In fact, he should be convinced even if she answers correctly with
probability substantially larger than 50%, because if the beer tastes the same
BPP
∪
NP
4
Goldstar is an Israeli beer, available in 330-ml and 500-ml bottles. Actually, the story traces back to Athena's
claim regarding jars of nectar, which was contested by Zeus himself. Unfortunately, Ovid does not tell the outcome
of their interaction.
