Cryptography Reference
In-Depth Information
that the oversimplified version does
not
imply the basic version (i.e., Definition 4.3.2);
consider, for example, a prover that on common input
x
sends some hard-to-compute
poly(
|
x
|
)-bit-long string that depends only on
|
x
|
(e.g., the prime-factorization of all
integers in the interval [2
|
x
|
+
1
,...,
2
|
x
|
+|
x
|
3
]).
4.3.4. Sequential Composition of Zero-Knowledge Proofs
An intuitive requirement that a definition of zero-knowledge proofs must satisfy is that
zero-knowledge proofs should be closed under sequential composition. Namely, if we
execute one zero-knowledge proof after another, then the composed execution must
be zero-knowledge. The same should remain valid even if we execute polynomially
many proofs one after the other. Indeed, as will be shown shortly, the revised defini-
tion of zero-knowledge (i.e., Definition 4.3.10) satisfies this requirement. Interestingly,
zero-knowledge proofs as defined in Definition 4.3.2 are not closed under sequential
composition, and this fact is indeed another indication of the necessity of augmenting
this definition (as done in Definition 4.3.10).
In addition to its conceptual importance, the sequential-composition lemma is an
important tool in the design of zero-knowledge proof systems. Typically, such a proof
system consists of many repetitions of an atomic zero-knowledge proof. Loosely speak-
ing, the atomic proof provides
some
(but not much) statistical evidence for the validity
of the claim. By repeating the atomic proof sufficiently many times, the confidence
in the validity of the claim is increased. More precisely, the atomic proof offers a gap
between the acceptance probabilities for strings in the language and strings outside the
language. For example, in Construction 4.3.8, pairs of isomorphic graphs (i.e., inputs
in
GI
) are accepted with probability 1, whereas pairs of non-isomorphic graphs (i.e.,
inputs not in
GI
) are accepted with probability at most
1
2
. By repeating the atomic
proof, the gap between the two probabilities is further increased. For example, repeat-
ing the proof of Construction 4.3.8
k
times will yield a new interactive proof in which
inputs in
GI
are still accepted with probability 1, whereas inputs not in
GI
are accepted
with probability at most
1
2
k
. The sequential-composition lemma guarantees that if the
atomic-proof system is zero-knowledge, then so is the proof system resulting from
repeating the atomic proof polynomially many times.
Before we state the sequential-composition lemma, we remind the reader that the
zero-knowledge property of an interactive proof is actually a property of the prover.
Also, the prover is required to be zero-knowledge only on inputs in the language.
Finally, we stress that when talking about zero-knowledge with respect to auxiliary
input, we refer to all possible auxiliary inputs for the verifier.
Lemma 4.3.11 (Sequential-Composition Lemma):
Let P be an interactive
machine (i.e., a prover) that is
zero-knowledge with respect to auxiliary input
on some language L. Suppose that the last message sent by P, on input x , bears
a special end-of-proof symbol. Let Q
(
)
be a polynomial, and let P
Q
be an in-
teractive machine that, on common input x , proceeds in Q
(
ยท
)
phases, each
of them consisting of running P on common input x . (We stress that in case
P is probabilistic, the interactive machine P
Q
uses independent coin tosses for
216
|
x
|
