Cryptography Reference
In-Depth Information
·
input, respectively. Consider
th
e function B
x
,
z
,
r
(
)
describing the messages sent by
machine B such that B
x
,
z
,
r
(
m
)
denotes the message sent by B on commo
n i
nput
x , auxiliary input z, random input r , and sequence of incoming messages m. For
simplicity, we assume that the output of B appears as its last message.
Black-box simulator:
We say that a probabilistic polynomial-time oracle machine
Misa
black-box simulator
for the prover
P
and the language
L if for every
polynomial-time interactive machine B, every probabilistic polynomial-time or-
acle machine D, every polynomial p
(
·
)
, all sufficiently large x
∈
L, and every
}
∗
,
Pr
D
B
x
,
z
,
r
(
z
,
r
∈{
0
,
1
1
− Pr
D
B
x
,
z
,
r
M
B
x
,
z
,
r
(
x
)
=
1
<
1
P
,
B
r
(
z
)
(
x
))
=
p
(
|
x
|
)
where B
r
(
z
)
denotes the interaction of machine B with auxiliary input z and
random input r .
We say that P is
black-box zero-knowledge
if it has a black-box simulator.
Essentially, the definition says that a black-box simulator mimics the interaction of
prover
P
with any polynomial-time verifier
B
relative to any auxiliary input (i.e.,
z
)
that
B
may get and any random input (i.e.,
r
) that
B
may choose. The simulator
does so (efficiently) merely by using oracle calls to
B
x
,
z
,
r
(which specifies the next
message that
B
sends on input
x
, auxiliary input
z
, and random input
r
). The simula-
tion is indistinguishable from the true interaction even if the distinguishing algorithm
(i.e.,
D
) is given access to the oracle
B
x
,
z
,
r
. An equivalent formulation is presented in
Exercise 21. Clearly, if
P
is black-box zero-knowledge, then it is zero-knowledge with
respect to auxiliary input (and has polynomially bounded knowledge tightness, see
Definition 4.4.13).
Theorem 4.5.11:
Suppose that
(
P
,
V
)
is an interactive proof system
with negli-
gible error probability
for the language L. Further suppose that
(
P
,
V
)
has the
following properties:
Constant round
: There exists an integer k such that for every x
∈
L, on input x the
prover P sends at most k messages.
Public coins
: The messages sent by the verifier V are predetermined consecutive
segments of its random tape.
Black-box zero-knowledge
: The prover P has a black-box simulator (over the
language L).
Then L
∈
BPP
.
The theorem also holds for computationally sound zero-knowledge proof systems de-
fined and discussed in Section 4.8.
We remark that both Construction 4.3.8 (zero-knowledge proof for Graph Isomor-
phism) and Construction 4.4.7 (zero-knowledge proof for Graph Colorability) are
constant-round, use public coins, and are black-box zero-knowledge (for the corre-
sponding language). However, they
do not
have negligible error probability. Yet, re-
peating each of these constructions polynomially many times
in parallel
yields an
253
