Cryptography Reference
In-Depth Information
no resource bounds are placed on the computing power of the prover (in either com-
pleteness or soundness conditions). Third, as in the case of
, the error probability
in the foregoing definition can be made exponentially small by repeating the interaction
(polynomially) many times.
Every language in
BPP
,
and let
R
L
be a witness relation associated with the language
L
(i.e.,
R
L
is recognizable
in polynomial time, and
L
equals the set
NP
has an interactive proof system. Specifically, let
L
∈
NP
{
x
:
∃
y
s.t.
|
y
|=
poly(
|
x
|
)
∧
(
x
,
y
)
∈
R
L
}
).
Then an interactive proof for the language
L
consists of a prover that on input
x
L
sends a witness
y
(as before), and a verifier that upon receiving
y
(on common input
x
)
outputs 1 if
∈
R
L
(and outputs 0 otherwise). Clearly, when
interacting with the prescribed prover, this verifier will always accept inputs in the
language. On the other hand, no matter what a cheating “prover” does, this verifier will
never accept inputs not in the language. We point out that in this specific proof system,
both parties are deterministic (i.e., make no use of their random tapes). It is easy to see
that only languages in
|
y
|=
poly(
|
x
|
) and (
x
,
y
)
∈
NP
have interactive proof systems in which both parties are
deterministic (see Exercise 2).
In other words,
NP
can be viewed as a class of interactive proof systems in which
the interaction is unidirectional (i.e., from the prover to the verifier) and the verifier
is deterministic (and never errs). In general interactive proofs,
both
restrictions are
waived: The interaction is bidirectional, and the verifier is probabilistic (and may err,
with some small probability). Both bidirectional interaction and randomization seem
essential to the power of interactive proof systems (see Exercise 2).
IIP
IP
Definition 4.2.5 (The Class
):
The class
consists of all languages having
interactive proof systems.
By the foregoing discussion,
can be viewed
as each having a verifier that decides on membership without any interaction, it follows
that
NP
⊆
IP
. Because languages in
BPP
BPP
∪
NP
⊆
IP
. We remind the reader that it is not known whether or not
BPP
⊆
NP
.
We next show that the definition of the class
remains invariant if we replace the
(constant) bounds in the completeness and soundness conditions with two functions
c
,
s
:
IP
N →
[0
,
1] satisfying
c
(
n
)
<
1
−
2
−
poly(
n
)
,
s
(
n
)
>
2
−
poly(
n
)
, and
c
(
n
)
>
s
(
n
)
+
1
poly(
n
)
. Namely, we consider the following generalization of Definition 4.2.4.
Definition 4.2.6 (Generalized Interactive Proof ):
Let
c
,
s
:
N → R
be func-
tions satisfying
c
(
n
)
1
p
(
n
)
)
. An interactive pair
(
P
,
V
)
is called a (generalized) interactive proof system for the language L, with
completeness bound
c
(
>
s
(
n
)
+
for some polynomial p
(
·
·
)
and
soundness bound
s
(
·
)
,if
(modified) completeness:
for every x
∈
L,
Pr
P
,
V
(
x
)
=
1
]
≥
c
(
|
x
|
)
[
(modified) soundness:
for every x
∈
L and every interactive machine B,
Pr
[
B
,
V
(
x
)
=
1]
≤
s
(
|
x
|
)
