Cryptography Reference
In-Depth Information
We stress that the time-complexity, so defined, is independent of the content of the
messages that machine
A
receives. In other words, it is an upper bound that holds for
all possible incoming messages (as well as all internal coin tosses). In particular, an
interactive machine with time-complexity
t
(
·
) may read, on input
x
, only a prefix of
total length
t
(
|
x
|
) of the messages sent to it.
4.2.1.3. Proof Systems
In general, proof systems are defined in terms of the verification procedure (which can
be viewed as one entity, called the verifier). A “proof” for a specific claim is always
considered as coming from the outside (which can be viewed as another entity, called
the prover). The verification procedure itself does not generate “proofs,” but merely
verifies their validity. Interactive proof systems are intended to capture whatever can
be efficiently verified via interaction with the outside. In general, the interaction with
the outside can be very complex and may consist of many message exchanges, as long
as the total time spent by the verifier is polynomial (in the common input).
Our choice to consider probabilistic polynomial-time verifiers is justified by the
association of efficient procedures with probabilistic polynomial-time algorithms. Fur-
thermore, the verifier's verdict of whether to accept or reject the claim is probabilistic,
and a bounded error probability is allowed. (Jumping ahead, we mention that the error
can be decreased to be negligible by repeating the verification procedure sufficiently
many times.)
Loosely speaking, we require that the prover be able to convince the verifier of
the validity of true statements, while nobody can fool the verifier into believing false
statements. Both conditions are given a probabilistic interpretation: It is required that
the verifier accept valid statements with “high” probability, whereas the probability
that it will accept a false statement is “low” (regardless of the machine with which the
verifier interacts). In the following definition, the verifier's output is interpreted as its
decision on whether to accept or reject the common input. Output 1 is interpreted as
“accept,” whereas output 0 is interpreted as “reject.”
Definition 4.2.4 (Interactive Proof System):
A pair of interactive machines
(
P
V
)
is called an
interactive proof system for a language
L if machine V is
polynomial-time and the following two conditions hold:
,
Completeness:
For every x
∈
L,
2
3
Pr
[
P
,
V
(
x
)
=
1]
≥
Soundness:
For every x
∈
L and every interactive machine B,
1
3
Pr
[
B
,
V
(
x
)
=
1]
≤
Some remarks are in order. We first stress that the soundness condition refers to all poten-
tial “provers,” whereas the completeness condition refers only to the prescribed prover
P
. Second, the verifier is required to be a (probabilistic) polynomial-time machine, but
