Zero-Knowledge Proof Systems - Foundations of Cryptography: Basic Tools - page 251

We stress that Theorem 4.5.8 does not apply to perfect (or statistical) zero-knowledge
arguments , defined and discussed in Section 4.8. Hence, there is no conflict between
Theorem 4.5.8 and the fact that under some reasonable complexity assumptions, perfect
zero-knowledge arguments do exist for every language in NP .

4.5.4. Zero-Knowledge and Parallel Composition

We present two negative results regarding parallel composition of zero-knowledge
protocols. These results are very different in terms of their conceptual standing: The
first result asserts the failure (in general) of the parallel-composition conjecture (i.e.,
the conjecture that running any two zero-knowledge protocols in parallel will result
in a zero-knowledge protocol), but says nothing about specific natural candidates. The
second result refers to a class of interactive proofs that contains several interesting
and natural examples, and it asserts that the members of this class cannot be proved
zero-knowledge using a general paradigm (known by the name “black-box simulation”).
The relation of the second result to this subsection follows from the fact that some of the
members in this class are obtained by parallel composition of natural zero-knowledge
proofs. We mention that it is hard to conceive an alternative way of demonstrating the
zero-knowledge property of protocols (other than by providing a black-box simulator).
We stress that by “parallel composition” we mean playing several copies of the pro-
tocol in parallel, where the prescribed (honest) parties execute each copy independently
of the other copies. Specifically, if a party is required to toss coins in a certain round,
then it will toss independent coins for each of the copies.

4.5.4.1. Failure of the Parallel-Composition Conjecture

As a warning about trusting unsound intuitions, we mention that for several years
(following the introduction of zero-knowledge proofs) some researchers insisted that
the following must be true:

Parallel-Composition Conjecture: Let P 1 and P 2 be two zero-knowledge pro-
vers. Then the prover that results from running both of them in parallel is also
zero-knowledge.

However, the parallel-composition conjecture is simply wrong.

Proposition 4.5.9: There exist two provers, P 1 and P 2 , such that each is zero-
knowledge, and yet the prover that results from running both of them in parallel
yields knowledge (e.g., a cheating verifier can extract from this prover a solution
to a problem that is not solvable in polynomial time). Furthermore, the foregoing
holds even if the zero-knowledge property of each of the P i 's can be demonstrated
with a simulator that uses the verifier as a black box (as in Definition 4.5.10).

Proof Idea: Consider a prover, denoted P 1 , that sends “knowledge” to the ver-
ifier if and only if the verifier can answer some randomly chosen hard question
(i.e., we stress that the question is chosen by P 1 ). Answers to such hard questions
251