Cryptography Reference
In-Depth Information
If a statement is true (false), then there may be a
proof
that further explains why
(i.e., according to which semantic rules) the statement is true (false). If such a proof
exists, then it can typically also be represented and expressed as a string.
A conventional (i.e., noninteractive)
proof system
is a system in which state-
ments and proofs can be expressed and efficiently verified. This means that part of
the system is an efficient (proof verification) algorithm that takes as input a statement
and a proof and that generates as output a binary decision (i.e., the statement is true
or false). If the output is true, then the proof is valid for the statement. If, however,
the output is false, then the proof is not valid for the statement. In addition to the
efficiency requirement for the proof verification algorithm, one usually requires that
a particular proof system is also complete and sound.
Completeness:
A proof system is
complete
if for every valid proof the proof
verification algorithm outputs true (i.e., the proof is accepted).
Soundness:
A proof system is
sound
if for every invalid proof the proof verification
algorithm outputs false (i.e., the proof is rejected).
We mention but do not further address the results of Kurt Godel,
4
who showed
in the early 1930s that there are theories for which there is no proof system that is
complete and consistent, meaning that there are theories in which some statements
may not have a proof [21].
Contrary to a conventional proof, an
interactive proof
is a(n interactive)
protocol that can be used by a prover to prove a statement to a verifier. Formally
speaking, the prover and the verifier are probabilistic algorithms or probabilistic
Turing machines. The verifier is assumed to be polynomially bound, whereas one
usually doesn't make such an assumption on the prover's side. Needless to say,
an interactive proof that is efficient for the prover is practically more useful than
an interactive proof that is inefficient. If the soundness requirement assumes a
polynomially bound prover (in addition to the polynomially bound verifier), then
the protocol is called an
interactive argument
(instead of an interactive proof). In
either case, the prover and the verifier must exchange messages during the execution
of the protocol, and at the end the verifier must decide whether the proof is valid
(i.e., accepted) or not (i.e., rejected).
Again, we require that an interactive proof and a corresponding
interactive
proof system
is complete and sound. Because we are now in a probabilistic world,
we must say that the interactive proof system is complete if the verifier accepts every
true statement with an overwhelmingly large probability, and that the interactive
proof system is sound if the verifier rejects every false statement (i.e., if the
verifier accepts a false statement only with a probability that is negligibly small).
4K rt Godel was a German mathematician who lived from 1906 to 1978.
