Cryptography Reference
In-Depth Information
Jumping ahead, we mention that all the results presented in this section, except
Theorem 4.5.8 (i.e., the limitation of perfect zero-knowledge proofs), apply also to
zero-knowledge arguments as defined and discussed in Section 4.8.
4.5.1. On the Importance of Interaction and Randomness
We call a proof system
trivial
if it is a proof system for a language in
BPP
.
Because languages in
can be decided by the verifier without any interaction
with the prover, such proof systems are of no use (at least as far as cryptography is
concerned).
BPP
On the Triviality of Unidirectional Zero-Knowledge Proofs.
A
unidirectional
proof
system is one in which a single message is sent (i.e., from the prover to the verifier).
We show that such proof systems, which constitute a special class of interactive proofs
that includes
NP
-type proofs as special cases, are too restricted to allow non-trivial
zero-knowledge proofs.
Theorem 4.5.1:
Suppose that L has a unidirectional zero-knowledge proof
system. Then L
∈
BPP
.
Proof Idea:
Given a simulator
M
for the view of the honest verifier in this system
(as guaranteed by Definition 4.3.3), we construct a decision procedure for
L
.On
input
x
,weinvoke
M
(
x
) and obtain (
w,
r
), where
w
supposedly is a message sent
}
supposedly is the random tape of the verifier. We
by the prover and
r
∈{
0
,
1
uniformly select
r
∈{
}
and decide as the true verifier would have decided
upon receiving the message
w
and using
r
as the content of its random tape.
The hypothesis that
M
is a good simulator is used in the analysis of the case
x
∈
L
, whereas the soundness of the proof system (and the fact that
r
is selected
independently of
w
) is used for the case
x
∈
L
.
0
,
1
On the Essential Role of the Verifier's Randomness.
We next show that randomiza-
tion on the verifier's part is necessary for the non-triviality of zero-knowledge proof
systems. It follows that a non-zero error probability is essential to the non-triviality
of zero-knowledge proof systems, because otherwise the verifier could always set its
random tape to be all zeros. (In fact, we can directly prove that a non-zero sound-
ness error is essential to the non-triviality of zero-knowledge proof systems and derive
Theorem 4.5.2 as a special case.
15
)
Theorem 4.5.2:
Suppose that L has a zero-knowledge proof system in which the
verifier program is deterministic. Then L
∈
BPP
.
15
Again, given a simulator
M
for the view of the honest verifier in this system, we construct a decision
procedure for
L
. On input
x
, we invoke
M
(
x
) and accept if and only if the output corresponds to a transcript that
the honest verifier would have accepted. The hypothesis that
M
is a good simulator is used in the analysis of the
case
x
∈
L
, whereas the
perfect
soundness of the proof system is used for the case
x
∈
L
. Theorem 4.5.2 follows
because deterministic verifiers necessarily have zero soundness error.
