Cryptography Reference
In-Depth Information
Proof Idea:
Because the verifier is deterministic, the prover can fully determine
each of its future messages. Thus the proof system can be converted into an equiv-
alent one in which the prover simply sends to the verifier the full transcript of
an execution in the original proof system. Observe that the completeness, sound-
ness, and zero-knowledge properties of the original proof system are preserved
and that the resulting proof system is unidirectional. We conclude by applying
Theorem 4.5.1.
On the Essential Role of the Prover's Randomness.
Finally, we show that random-
ization on the prover's part is also necessary for the non-triviality of zero-knowledge
proof systems.
Theorem 4.5.3:
Suppose that L has an
auxiliary-input
zero-knowledge proof
system in which the prover program is deterministic. Then L
∈
BPP
.
Note that the hypothesis (i.e., the type of zero-knowledge requirement) is stronger here.
(Computationally unbounded deterministic provers may suffice for the non-triviality
of the bare definition of zero-knowledge (i.e., Definition 4.3.2).)
Proof Idea:
Suppose, without loss of generality, that the verifier is the party
sending the first message in this proof system. We consider a cheating verifier
that given an auxiliary input
z
1
,...,
z
t
sends
z
i
as its
i
th message. The remaining
messages of this verifier are determined arbitrarily. We first observe that because
the prover is deterministic, in a real interaction the first
i
≤
t
responses of the
prover are determined by
z
1
,...,
z
i
. Thus, that must be essentially the case in
the simulation. We construct a decision procedure for
L
by emulating the in-
teraction of the prescribed prover with the prescribed verifier on common input
equal to the input to the procedure, denoted
x
. Toward this end, we uniformly
select and fix a random tape, denoted
r
, for the verifier. The emulation pro-
ceeds in iterations corresponding to the prover's messages. To obtain the prover's
next message, we first determine the next verifier message (by running the pro-
gram of the prescribed verifier on input
x
, coins
r
, and incoming messages as
recorded thus far). Next, we invoke the simulator on input (
x
,
(
z
1
,...,
z
i
)), where
z
1
,...,
z
i
are the verifier's messages determined thus far, and so we obtain and
record the prover's
i
th message. Our final decision is determined by the verifier's
decision.
4.5.2. Limitations of Unconditional Results
Recall that Theorem 4.4.12 asserts the existence of zero-knowledge proofs for all lan-
guages in
,
provided that non-uniformly one-way functions exist
. In this subsection
we consider the question of whether or not this sufficient condition is also neces-
sary. The following results seem to provide some (yet, weak) indication in that direc-
tion. Specifically, the existence of zero-knowledge proof systems for languages
outside of
IP
BPP
implies (very weak) forms of one-wayness. In a dual way, the
248
