Cryptography Reference
In-Depth Information
providing the proof. In contrast, the notion of a verifier tends to be more explicit in such
discussions, which typically emphasize the
verification process
, or in other words the
role of the verifier. Both in mathematics and in real-life situations, proofs are defined
in terms of the verification procedure. The verification procedure is considered to be
relatively simple, and the burden is placed on the party/person supplying the proof (i.e.,
the prover).
The asymmetry between the complexity of the verification task and the complexity
of the theorem-proving task is captured by the complexity class
NP
, which can be
viewed as a class of proof systems. Each language
L
∈
NP
has an efficient verification
procedure for proofs of statements of the form “
x
∈
L
.” Recall that each
L
∈
NP
is
characterized by a polynomial-time-recognizable relation
R
L
such that
L
={
x
:
∃
y
s.t. (
x
,
y
)
∈
R
L
}
and (
x
,
y
)
∈
R
L
only if
|
y
|≤
poly(
|
x
|
). Hence, the verification procedure for member-
ship claims of the form “
x
L
” consists of applying the (polynomial-time) algorithm
for recognizing
R
L
to the claim (encoded by)
x
and a prospective proof, denoted
y
.Any
y
satisfying (
x
∈
,
y
)
∈
R
L
is considered a
proof
of membership of
x
∈
L
. Thus, correct
statements (i.e.,
x
L
) and only these have proofs in this proof system. Note that the
verification procedure is “easy” (i.e., polynomial-time), whereas coming up with proofs
may be “difficult” (if indeed
∈
NP
BPP
).
It is worthwhile to note the “distrustful attitude” toward the prover that underlies any
proof system. If the verifier trusts the prover, then no proof is needed. Hence, whenever
discussing a proof system, one considers a setting in which the verifier is not trusting
the prover and furthermore is skeptical of anything the prover says.
is not contained in
4.1.1.3. Completeness and Soundness
Two fundamental properties of a proof system (i.e., a verification procedure) are its
soundness
(or
validity
) and
completeness
. The soundness property asserts that the ver-
ification procedure cannot be “tricked” into accepting false statements. In other words,
soundness
captures the verifier's ability to protect itself from being convinced of false
statements (no matter what the prover does in order to fool the verifier). On the other
hand,
completeness
captures the ability of some prover to convince the verifier of true
statements (belonging to some predetermined set of true statements). Note that both
properties are essential to the very notion of a proof system.
We remark here that not every set of true statements has a “reasonable” proof sys-
tem in which each of those statements can be proved (while no false statement can be
“proved”). This fundamental fact is given precise meaning in results such as
G odel's
Incompleteness Theorem
and
Turing's
theorem regarding the
undecidability of the
Halting Problem
. We stress that in this chapter we confine ourselves to the class of
sets (of valid statements) that do have “efficient proof systems.” In fact, Section 4.2 is
devoted to discussing and formulating the concept of “efficient proof systems.” Jump-
ing ahead, we hint that the efficiency of a proof system will be associated with the
efficiency of its verification procedure.
