Cryptography Reference
In-Depth Information
look pseudorandom, yet
P
1
(which is not computationally bounded) can verify
their correctness. Now consider a second (computationally unbounded) prover,
denoted
P
2
, that answers these hard questions. Each of these provers (by itself) is
zero-knowledge:
P
1
is zero-knowledge because it is unlikely that any probabilistic
polynomial-time verifier can answer its questions, whereas
P
2
is zero-knowledge
because its answers can be simulated by random strings. Yet, once they are played
in parallel, a cheating verifier can answer the question of
P
1
by sending it to
P
2
and
using the answer obtained from
P
2
to gain knowledge from
P
1
. To turn this idea
into a proof we need to construct a hard problem with the previously postulated
properties.
The foregoing proposition refutes the parallel-composition conjecture by means of
exponential-time provers. Assuming the existence of one-way functions, the parallel-
composition conjecture can also be refuted for probabilistic polynomial-time provers
(with auxiliary inputs). For example, consider the following two provers
P
1
and
P
2
,
which make use of proofs of knowledge (see Section 4.7). Let
C
be a bit-commitment
scheme (which we know to exist provided that one-way functions exist). On common
input
C
(1
n
,σ
), where
σ
∈{
0
,
1
}
, prover
P
1
proves to the verifier, in zero-knowledge,
that it knows
. (To this end the prover is given as auxiliary input the coins used in
the commitment.) In contrast, on common input
C
(1
n
σ
,σ
), prover
P
2
asks the verifier
to prove that it knows
to the verifier. This
verifier employs the same proof-of-knowledge system used by the prover
P
1
. Clearly,
each prover is zero-knowledge, and yet their parallel composition is not.
Similarly, using stronger intractability assumptions, one can also refute the parallel-
composition conjecture with respect to almost-perfect zero-knowledge (rather than
with respect to computational zero-knowledge). (Here we let the provers use a perfect
zero-knowledge, computationally sound proof of knowledge; see Section 4.8.)
σ
, and if
P
2
is convinced, then it sends
σ
4.5.4.2. Problems Occurring with “Natural” Candidates
By definition, to show that a prover is zero-knowledge, one has to present, for each
prospective verifier
V
∗
, a corresponding simulator
M
∗
(which simulates the interac-
tion of
V
∗
with the prover). However, all known demonstrations of zero-knowledge
proceed by presenting one “universal” simulator that uses any prospective verifier
V
∗
as a black box. In fact, these demonstrations use as a black box (or oracle) the next-
message function determined by the verifier program (i.e.,
V
∗
), its auxiliary input, and
its random input. (This property of the simulators is implicit in our constructions of the
simulators in previous sections.) We remark that it is hard to conceive an alternative
way of demonstrating the zero-knowledge property (because a non-black-box usage of
a verifier seems to require some “reverse engineering” of its code). This difficulty is
greatly amplified in the context of auxiliary-input zero-knowledge.
Definition 4.5.10 (Black-Box Zero-Knowledge):
and
r be strings representing a common input, an auxiliary input, and a random
Next-message function:
Let B be an interactive Turing machine, and let x
,
z
,
